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. http://leetcode.com/onlinejudge#question_86

leetcode_partition_list.cpp

/**
 * 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* cur = head;
        ListNode* tag = head;
        while (cur != NULL) {
            if (cur->val < x) {
                ListNode* tmp = tag;
                int k = tmp->val;
                while (tmp != cur) {
                    swap(tmp->next->val, k);
                    tmp = tmp->next;
                }
                tag->val = k;
                tag = tag->next;
            }
            cur = cur->next;
        }
        return head;
    }
};