首页 > 代码库 > leetcode. Partition List

leetcode. 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.

类似于款速排序中的分割算法。

因为是链表,不能使用从两头向中间扫描,而应使用从前向后扫描,详见算法导论 快速排序。

 1 ListNode *partition(ListNode *head, int x)  2     { 5         ListNode *dummy = new ListNode(INT_MIN), *p, *q, *r; 6         dummy->next = head; 7          8         p = dummy; 9         q = dummy;10         while (q->next != NULL)11         {12             if (q->next->val < x)13             {14                 if (p == q)15                 {16                     p = p->next;17                     q = q->next;18                     continue;19                 }20                 r = q->next;21                 q->next = r->next;22                 r->next = p->next;23                 p->next = r;24                 p = r;25             }26             else27             {28                 q = q->next;29             }30         }31         32         p = dummy->next;33         delete dummy;34         return p;35     }

 

leetcode. Partition List