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.
将链表分割成两部分，大于某个数字的在左侧，小于等于某个数字的在右侧，用的方法比较蠢可能就是遍历一次分成两个链表，然后再将它们接起来。具体代码如下所示：
1 class Solution { 2 public: 3 ListNode* partition(ListNode* head, int x) { 4 ListNode * helper1 = new ListNode(INT_MIN); 5 ListNode * helper2 = new ListNode(INT_MIN); 6 ListNode * p1 = helper1; 7 ListNode * p2 = helper2; 8 while(head){ 9 if(head->val < x){ 10 p1->next = head; 11 head = head->next; 12 p1 = p1->next; 13 p1->next = NULL; 14 }else{ 15 p2->next = head; 16 head = head->next; 17 p2 = p2->next; 18 p2->next = NULL; 19 } 20 } 21 p1->next = helper2->next; 22 return helper1->next; 23 } 24 };
LeetCode OJ：Partition List（分割链表）
原文：http://www.cnblogs.com/-wang-cheng/p/5005298.html