[LeetCod] 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.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.
Analysis:
We need to maintain two points -- one for the tail of the nodes which are less than x, the other for the tail of the node which are greater than or equal to x. Loop the list, for any node, it will be following either of the tails.

/**
 * 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 dummy(0);
        ListNode *sTail = &dummy, *lTail;
        sTail->next = head;
        ListNode *p = head;
        while(p)
        {
            if(p->val < x)
            {
                if(sTail->next != p)
                {
                    lTail->next = p->next;
                    p->next = sTail->next;
                    sTail->next = p;
                }
                sTail = p;
            }
            else
            {
                lTail = p;
            }
            p = p->next;
        }
        return dummy.next;
    }
};