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.

 

使用两个链表newHead1, newHead2，遍历原链表，如果结点值小于x，则挂在newHead1上，如果大于等于x，则挂在newHead2上，最后把newHead2挂在newHead1上。

 

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* newHead1 = new ListNode(0);13         ListNode* newHead2 = new ListNode(0);14         15         ListNode* pNode1 = newHead1;16         ListNode* pNode2 = newHead2;17         18         ListNode* pNode = head;19         20         while(pNode){21             if(pNode->val < x){22                 pNode1->next = pNode;23                 pNode1 = pNode1->next;24             }else{25                 pNode2->next = pNode;26                 pNode2 = pNode2->next;27             }28             pNode = pNode->next;29         }30         31         pNode2->next = NULL;32         pNode1->next = newHead2->next;33         34         return newHead1->next;35     }36 };