86. 分隔链表

给你一个链表和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例：

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

---

题解：

使用两个链表分别保存 小于x 的节点 和 大于等于x的节点，节点不需要重新开辟内存，直接将指针指向原链表上的节点即可。最后将两个链表拼接在一起。

时间复杂度： O ( n ) O(n) O(n)

额外空间复杂度： O ( 1 ) O(1) O(1)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        if ( !head || !head->next ) return head;
        ListNode *low = nullptr, *high = nullptr;
        ListNode *h1 = nullptr, *h2 = nullptr;
        for ( ListNode *p = head; p; p = p->next ) {
            if ( p->val < x ) {
                if ( !low ) {
                    h1 = low = p;
                } else {
                    low->next = p;
                    low = p;
                }
            } else {
                if ( !high ) {
                    h2 = high = p;
                } else {
                    high->next = p;
                    high = p;
                }
            }
        }
        if ( h1 && h2 ) {
            if( high->next ) 
                high->next = nullptr;
            low->next = h2;
            return h1;
        } else if ( h1 ) return h1;
        else return h2;
    }
};
时间：4ms，击败：96.68%
内存：9.8MB，击败：16.88%