Programming Skills: Partition List

[題目]
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

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

Example:

Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5

list中有兩批人，大於等於3的人(4,3,5)和小於3的人(1,2,2)。請把(1,2,2)這批人移到另一批人(4,3,5)的前面。這兩批人內部的順序保持不變(4,3,5這個順序不變，1,2,2這個順序不變)。
這題來自於leetcode大家可以直接去leetcode寫然後跑online judge
https://leetcode.com/problems/partition-list/description/

[思路]
1.分群:
把link list掃瞄一遍，自然可看出每個人是否小於3

2.調整位置:
掃描的過程中小於3的人要拔出來，插到前面。
問題是插到前面哪裡? 它要求內部順序不變，所以不能插到list head。
那麼我們就想，大於等於3的這群人(4,3,5)中的第一個是4，我們只要把小於3的人都插到4前面就可以了。

於是我們先掃描list找出第一個遇到大於等於3的人(也就是4)，把4的previous node記起來(稱之為smalltail)。接著繼續掃描，每次遇到小於3的人就插到smalltail後面，然後更新smalltail即可。


/**
 * 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 d(-1);
        d.next=head;
        ListNode* smalltail = &d;
        while(smalltail->next!=NULL && smalltail->next->val < x){
            smalltail = smalltail->next;
        }
        ListNode* cur=smalltail;
        while(cur->next){
            //continue scanning, if cur->next belong to "samll set",
            //remove cur->next, and insert cur->next to smalltail.
            if(cur->next->val < x) {
                ListNode* tmp=cur->next;
                cur->next = tmp->next;
                tmp->next=smalltail->next;
                smalltail->next=tmp;
                smalltail=smalltail->next;
            }
            else{
                cur=cur->next;
            }
        }
        return d.next;
        
    }
};