LeetCode-86. 分隔链表-Java-medium

题目链接

法一

    /**
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     * 类似于插入排序，将链表看成前后两部分，前面是小于x的结点，用tail指向这部分的尾结点
     * 每当遍历到小于x的结点就将它插入到前部分的尾部
     *
     * @param head
     * @param x
     * @return
     */
    public ListNode partition(ListNode head, int x) {
        ListNode dummy = new ListNode(0, head);
        ListNode tail = dummy, pre = dummy, cur = head;
        while (cur != null) {
            if (cur.val < x) { // 将当前结点脱离原来位置并插入到前一部分尾节点的后面
                pre.next = cur.next;  // pre跳过当前结点，与当前节点的next直接连接
                cur.next = tail.next; // 当前结点的next指向前一部分尾节点后面的结点
                tail.next = cur;      // 前一部分尾节点的next指向当前结点
                tail = tail.next;     // 前一部分尾节点后移
            }
            pre = cur;      // pre指向当前结点
            cur = cur.next; // 当前结点后移
        }
        return dummy.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

本地测试

        /**
         * 86. 分隔链表
         */
        lay.showTitle(86);
        Solution86 sol86 = new Solution86();
        int[] nums86 = new int[]{1, 4, 3, 2, 5, 2};
        ListNode head86 = new ListNode();
        head86 = listOpt.creatListByArray(head86, nums86);
        listOpt.showList(head86);
        int x86 = 3;
        System.out.println(x86);
        head86 = sol86.partition(head86.next, x86);
        listOpt.showNoHeadList(head86);
1
2
3
4
5
6
7
8
9
10
11
12
13