Partition List

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。

我们可以使用两个链表，p1和p2，以此遍历原链表，如果节点的值小于x，就挂载到p1下面，反之则放到p2下面，最后将p2挂载到p1下面就成了。

代码如下：

  1. class Solution {
  2. public:
  3.     ListNode *partition(ListNode *head, int x) {
  4.         ListNode dummy1(0), dummy2(0);
  5.         ListNode* p1 = &dummy1;
  6.         ListNode* p2 = &dummy2;
  8.         ListNode* p = head;
  9.         while(p) {
  10.             if(p->val < x) {
  11.                 p1->next = p;
  12.                 p1 = p1->next;
  13.             } else {
  14.                 p2->next = p;
  15.                 p2 = p2->next;
  16.             }
  17.             p = p->next;
  18.         }
  20.         p2->next = NULL;
  21.         p1->next = dummy2.next;
  22.         return dummy1.next;
  23.     }
  24. };