原创内容，转载请注明原文网址：http://homeqin.cn/a/wenzhangboke/jishutiandi/2018/1009/55.html

给定一个值，将链表小于该值得结点放到左边，大于该值得放到右边

例如：

Given 1->4->3->2->5->2 and x = 3,

return 1->2->2->4->3->5.

思路：分别将值大于小于给定值得结点生成另外两个链表，最后再将这两个链表相连

代码：

 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         ListNode *list1 = new ListNode(0);

13         ListNode *list2 = new ListNode(0);

14         ListNode *before = list1, *after = list2;

15         while(head)

16         {

17             if(head->val < x)

18             {

19                 before->next = head;

20                 before = before->next;

21             }

22             else

23             {

24                 after->next = head;

25                 after = after->next;

26             }

27             head = head->next;

28         }

29         after->next = NULL;

30         before->next = list2->next;

31         return list1->next;

32     }

33 };