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 ListNode *partition(ListNode *head, int x)  2     { 3         ListNode dummy = ListNode(INT_MIN), *p, *q, *r; 4         dummy.next = head; 5          6         p = &dummy; 7         q = &dummy; 8         while (p->next != NULL) 9         {10             if (p->next->val < x)11             {12                 if (p == q)13                 {14                     p = p->next;15                     q = q->next;16                 }17                 else18                 {19                     r = p->next;20                     p->next = r->next;21                     r->next = q->next;22                     q->next = r;23                     q = r;24                 }25             }26             else27             {28                 p = p->next;29             }30         }31         32         return dummy.next;33     }