题目描述

给定一个链表和一个数 $x$，请将链表中所有小于 $x$ 的数放到大于等于 $x$ 的数的左边。
请保持两部分中数的相对顺序不变。

样例

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

算法

(线性扫描) $O(n)$

定义两个头结点 $before, after$，分别存储两个部分对应的链表。
然后遍历原链表，对于每个节点，如果小于 $x$，则插入 $before$ 链表的结尾；否则，插入 $after$ 链表的结尾。
最后将 $after$ 链表插入 $before$ 链表的结尾。

时间复杂度分析：原链表只遍历一次，所以时间复杂度是 $O(n)$。

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode *before = new ListNode(0);
        ListNode *after = new ListNode(0);
        ListNode *pb = before, *pa = after;

        for (ListNode *p = head; p; p = p->next)
            if (p->val < x)
            {
                pb->next = p;
                pb = p;
            }
            else
            {
                pa->next = p;
                pa = p;
            }

        pb->next = after->next;
        pa->next = 0;

        return before->next;
    }
};