Leetcode算法Java全解答--86. 分隔链表

ゝ一纸荒年。 2022-04-03 14:07 117阅读 0赞

# Leetcode算法Java全解答–86. 分隔链表 #

### 文章目录 ###

*  Leetcode算法Java全解答--86. 分隔链表
 *   *  题目
     *  想法
     *  结果
     *  总结
     *  代码
     *   *  我的答案
         *  大佬们的答案
         *  测试用例
     *  其他

## 题目 ##

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例:

输入: head = 1->4->3->2->5->2, x = 3
    输出: 1->2->2->4->3->5

## 想法 ##

1.  搞2个指针，第一个指针表示达标的最后一个值，第二个值用来遍历整条链表，遍历完也结束了

第一个指针表示达标的最后一个值：index1的前面的值都要小于x

1.  使用2个链表，后面拼起来，在better方法里面

## 结果 ##

超过80%的测试案例

时间复杂度/空间复杂度：n/1

## 总结 ##

## 代码 ##

### 我的答案 ###

public ListNode partition(ListNode head, int x) {
        if (head == null || head.next == null || head.next.next == null) {
            return head;
        }
    
        ListNode result = head;
        ListNode slow = head;
        ListNode fast = head.next;
        ListNode preNode = head;
    
        while (fast != null) {
            if (fast.val < x) {
                if (result.val >= x) {
                    preNode.next = fast.next;
                    fast.next = result;
                    result = fast;
                    fast = preNode.next;
                    slow = result;
                    continue;
                }
    
                if (slow.next.equals(fast)) {
                    preNode = fast;
                    fast = fast.next;
                    slow = slow.next;
                } else {
                    preNode.next = fast.next;
                    fast.next = slow.next;
                    slow.next = fast;
                    // 前进
                    fast = preNode.next;
                    slow = slow.next;
                }
    
            } else {
                preNode = fast;
                fast = fast.next;
            }
        }
        return result;
    }

### 大佬们的答案 ###

public ListNode better(ListNode head, int x) {
            if (head == null || head.next == null) {
                return head;
            }
            ListNode head1 = new ListNode(0), cur1 = head1, head2 = new ListNode(1), cur2 = head2;
            while (head != null) {
                if (head.val >= x) {
                    cur2.next = head;
                    head = head.next;
                    cur2 = cur2.next;
                    cur2.next = null;
                } else {
                    cur1.next = head;
                    head = head.next;
                    cur1 = cur1.next;
                    cur1.next = null;
                }
            }
            cur1.next = head2.next;
            return head1.next;
        }

### 测试用例 ###

@Test
        public void test086() {
            // 创建测试案例
            ListNode listNode1 = new ListNode(1);
            ListNode listNode2 = new ListNode(4);
            ListNode listNode3 = new ListNode(3);
            ListNode listNode4 = new ListNode(2);
            ListNode listNode5 = new ListNode(5);
            ListNode listNode6 = new ListNode(2);
            listNode1.next = listNode2;
            listNode2.next = listNode3;
            listNode3.next = listNode4;
            listNode4.next = listNode5;
            listNode5.next = listNode6;
            int x1 = 3;
    
            // 测试案例期望值
            ListNode expResult11 = new ListNode(1);
            ListNode expResult12 = new ListNode(2);
            ListNode expResult13 = new ListNode(2);
            ListNode expResult14 = new ListNode(4);
            ListNode expResult15 = new ListNode(3);
            ListNode expResult16 = new ListNode(5);
            expResult11.next = expResult12;
            expResult12.next = expResult13;
            expResult13.next = expResult14;
            expResult14.next = expResult15;
            expResult15.next = expResult16;
    
            // 执行方法
            Solution086 solution086 = new Solution086();
            ListNode result1 = solution086.partition(listNode1, x1);
    
            // 判断期望值与实际值
            Assert.assertEquals(expResult11.toArray(), result1.toArray());
        }

## 其他 ##

代码托管码云地址：[https://gitee.com/lizhaoandroid/LeetCodeAll.git][https_gitee.com_lizhaoandroid_LeetCodeAll.git]

查看其他内容可以点击专栏或者我的博客哈：[https://blog.csdn.net/cmqwan][https_blog.csdn.net_cmqwan]

“大佬们的答案” 标签来自leetcode，侵权请联系我进行删改

如有疑问请联系，联系方式：QQ3060507060

[https_gitee.com_lizhaoandroid_LeetCodeAll.git]: https://gitee.com/lizhaoandroid/LeetCodeAll.git
[https_blog.csdn.net_cmqwan]: https://blog.csdn.net/cmqwan