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.

分析：

基本题，可以一次性通过。

解法：

class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @param x: an integer
     * @return: a ListNode 
     */
    ListNode *partition(ListNode *head, int x) {
        // write your code here
        ListNode dummySmallList(-1);
        ListNode dummyLargeList(-1);

        ListNode* currSmall = &dummySmallList;
        ListNode* currLarge = &dummyLargeList;

        while (head != NULL) {

            if (head->val < x) {
                currSmall->next = head;
                head = head->next;
                currSmall = currSmall->next;
                currSmall->next = NULL;
            } else {
                currLarge->next = head;
                head = head->next;
                currLarge = currLarge->next;
                currLarge->next = NULL;
            }
        }

        currSmall->next = dummyLargeList.next;

        return dummySmallList.next;
    }
};