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.
思路：新建两个头结点，分别把小于x 的节点链接到第一个头结点后，把大于或等于x 的节点链接到第二个头节点后。
时间复杂度O(n),空间复杂度O(1)
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution { 10 public: 11 ListNode *partition(ListNode *head, int x) { 12 if(head == NULL) return head; 13 14 ListNode *plow = new ListNode(-1); 15 ListNode *plhead = plow; 16 ListNode *phigh = new ListNode(-1); 17 ListNode *phhead = phigh; 18 ListNode *pt = head; 19 20 while (pt != NULL) { 21 if (pt->val < x) { 22 plow->next = pt; 23 plow = pt; 24 } else { 25 phigh->next = pt; 26 phigh = pt; 27 } 28 pt = pt->next; 29 } 30 31 plow->next = phhead->next; 32 phigh->next = NULL; 33 34 return plhead->next; 35 } 36 };
原文：http://www.cnblogs.com/vincently/p/4059341.html