分析

• 本题的考点：链表。

• 本题实际上是链表快排的其中一部分。思路也很直接，开两个虚拟头结点lh、rh，从前向后扫描链表，如果当前考察的节点p对应的val小于给定的x，将该节点接到左边的链表lh上，否则接到右侧的链表rh上。

• 遍历结束后，让lh的尾节点指向rh->next，最后返回lh->next即可。如下图：

代码

• C++

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {

        auto lh = new ListNode(-1), rh = new ListNode(-1);
        auto lt = lh, rt = rh;

        for (auto p = head; p; p = p->next) {
            if (p->val < x) lt = lt->next = p;
            else rt = rt->next = p;
        }
        lt->next = rh->next;
        rt->next = NULL;

        return lh->next;
    }
};

• Java

class Solution {
    public ListNode partition(ListNode head, int x) {

        ListNode lh = new ListNode(-1), rh = new ListNode(-1);
        ListNode lt = lh, rt = rh;

        for (ListNode p = head; p != null; p = p.next) {
            if (p.val < x) {
                lt.next = p;
                lt = lt.next;
            } else {
                rt.next = p;
                rt = rt.next;
            }
        }
        lt.next = rh.next;
        rt.next = null;

        return lh.next;
    }
}

时空复杂度分析

• 时间复杂度：$O(n)$，n为链表长度。

• 空间复杂度：$O(1)$。