问题描述：

Given a linked list and a value x, partition it such that all nodes less thanx come before nodes greater than or equal tox.

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.

基本思路：

类似链表快排算法的partition。

代码：

ListNode *partition(ListNode *head, int x) {  //C++
        if(head == NULL|| head->next == NULL)
            return head;
        
        ListNode tmphead(0);
        ListNode* result = &tmphead;
        
        result->next = head;
        ListNode* p = head;
        ListNode* pre = result;
        ListNode* tail = result;
        while(p != NULL)
        {
            if(p->val < x )
            {
                if(p == tail->next)
                {
                    pre = p;
                    p = p->next;
                    tail = tail->next;
                    
                    continue;
                }
                ListNode* tmp = p->next;
                ListNode* tmptail = tail->next;
                tail->next = p;
                p->next = tmptail;
                pre->next = tmp;
                
                tail = tail->next;
                p = tmp;    
                
            }
            else 
            {
                pre = p;
                p = p->next;
                
            }
            
        }
        return result->next;
            
    }

[leetcode]Partition List