题目描述

给定一个链表和一个数 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 代码

struct ListNode* partition(struct ListNode* head, int x){
    if (head == NULL || head->next == NULL) {
        return head;
    }

    struct ListNode *before = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode *after = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode *pb = before;
    struct ListNode *pa = after;

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

    pa->next = NULL;
    pb->next = after->next;
    pb = before->next;

    free(before);
    free(after);

    return pb;
}