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.将链表分逐个遍历，按大小分别加入ListL和ListR；
2.将ListL和ListR连接起来；
注意：1.ListL和ListR加入dummyNode可减少判断次数；
2.连接时ListL为空的情况；
3.ListR的tail->next要置为NULL；
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *partition(struct ListNode *head, int x) { struct ListNode *headL = ListNode(); struct ListNode *tailL = headL; struct ListNode *headR = ListNode(); struct ListNode *tailR = headR; while(head) { if(head->val < x) { tailL->next = head; tailL = tailL->next; } else { tailR->next = head; tailR = tailR->next; } head = head->next; } //set head must follow the join list step for the case listL is null tailL->next = headR->next; head = headL->next; free(headL); free(headR); tailR->next = NULL; return head; }
原文：http://www.cnblogs.com/Pseudocnblog/p/4304530.html
