【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 /**
 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 dummy_left(-1), dummy_right(-1);
13         ListNode *pl = &dummy_left, *pr = &dummy_right;
14         for (ListNode * p = head; p != nullptr; p = p->next) {
15             if (p->val < x) {
16                 pl->next = p;
17                 pl = pl->next;
18             } else {
19                 pr->next = p;
20                 pr = pr->next;
21             }
22         }
23         pl->next = dummy_right.next;
24         pr->next = nullptr;
25         return dummy_left.next;
26     }
27 };

View Code

维护两个链表，一个保存小于x的部分，一个保存大于x的部分，最后将两个链表拼接起来。要求保持稳定性则应该用尾插法。加dummy元素可使代码变简单。