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

思路：

由于不要求sort，只要求partition。可以建立一个新的list l2。遍历原list l1的每个节点p。

p->val < x，保留。

p->val >= x，从l1中移出并插入l2。

由于要删除节点需要使用被删节点的前节点。所以实际写的时候考察的是p->next->val和x的比较。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

class Solution { public: ListNode *partition(ListNode *head, int x) { ListNode *h1 = new ListNode(0); ListNode *h2 = new ListNode(0); ListNode *t2 = h2; h1->next = head; head = h1; while(head->next) { if(head->next->val<x) // skip node head = head->next; else { // remove node from h1 and insert to the tail of h2 t2->next = head->next; head->next = head->next->next; t2 = t2->next; t2->next = NULL; } } head->next = h2->next; head = h1->next; delete h1; delete h2; return head; } };

总结：
这类头节点经常要插入、删除的题目，第一反应就是试试使用dummy头节点来简化代码。