学步园

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

思路：

遍历整个链表，把大于等于x的和小于x的数据分别放在两个不同链表中，然后再将它们连接起来。

题解：

/**
 * 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) {
        if (head == nullptr)
            return nullptr;
    
        ListNode* larger_head = new ListNode(0);
        ListNode* larger_last = larger_head;
        
        ListNode* less_head = new ListNode(0);
        ListNode* less_last = less_head;
        
        auto push = [](ListNode*& last, ListNode* new_less)
        {
            last->next = new_less;
            last = last->next;
            last->next = nullptr;
        };
        
        ListNode* iter = head;
        while(iter != nullptr)
        {
            ListNode* next = iter->next;
            
            if (iter->val < x)
                push(less_last, iter);
            else
                push(larger_last, iter);
            
            iter = next;
        }
        
        // merge two lists
        if (less_last != less_head)
        {
            // less is not empty
            less_last->next = larger_head->next;
            delete larger_head;
            less_last = less_head->next;
            delete less_head;
            return less_last;
        }
        else
        {
            // less is empty
            delete less_head;
            larger_last = larger_head;
            larger_head = larger_head->next;
            delete larger_last;
            return larger_head;
        }
    }
};