题目

编写程序以 x 为基准分割链表，使得所有小于 x 的节点排在大于或等于 x 的节点之前。如果链表中包含 x，x 只需出现在小于 x 的元素之后(如下所示)。
分割元素 x 只需处于“右半部分”即可，其不需要被置于左右两部分之间。
https://leetcode-cn.com/problems/partition-list-lcci/
示例:

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

Related Topics 链表 双指针
👍 21 👎 0

分析及反思

双指针法，思路类似于“荷兰国旗🇳🇱”的颜色排序题目.
p指针左边必定是小于x的节点，q指针遍历链表，遇到val<x时，交换p,q的val，并且p=p.next

其中不需要保持原有的顺序，86题需要。所以有所异同。
https://leetcode-cn.com/problems/partition-list/

代码

该题 不需要保持原有顺序

info
解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:39.3 MB,击败了100.00% 的Java用户

class Solution {

    public ListNode partition(ListNode head, int x) {
        ListNode p, q;
        p = q = head;
        while (q != null) {
            if (q.val < x) {//肯定是大于等于的交换
                int t = q.val;
                q.val = p.val;
                p.val = t;
                p = p.next;
            }
            q = q.next;
        }
        return head;
    }
}

86题 保持后者的大小相对顺序

11:06 info
解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:39.2 MB,击败了5.55% 的Java用户

class Solution {
    public ListNode partition(ListNode head, int x) {
        //维护两条链表，利用尾插法保证相对顺序不变
        ListNode min = new ListNode(-1);
        ListNode max = new ListNode(-1);
        ListNode p = head, p1 = min, p2 = max;//mark 链表的头。

        while (p != null) {
            if (p.val < x) {
                min.next = p;
                min = min.next;
            } else {
                max.next = p;
                max = max.next;
            }
            p = p.next;
        }
        min.next = p2.next;//小的尾巴指向大的头部 尾插法
        max.next = null;///对于非空表，将尾结点指针域置空 否则 Error - Found cycle in the ListNode
        return p1.next;
    }
}