LeetCode

2013.12.26 22:58

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.

Solution:

　　This is a reversed process of merging two lists. Do it in one pass and watch out for nullptr.

　　Time complexity is O(n), space complexity is O(1).

Accepted code:

 1 // 2RE, 1AC, always keep an eye out for nullptr!
 2 /**
 3  * Definition for singly-linked list.
 4  * struct ListNode {
 5  *     int val;
 6  *     ListNode *next;
 7  *     ListNode(int x) : val(x), next(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     ListNode *partition(ListNode *head, int x) {
13         // IMPORTANT: Please reset any member data you declared, as
14         // the same Solution instance will be reused for each test case.
15         ListNode *l1 = nullptr, *l2 = nullptr;
16         ListNode *h1 = nullptr, *h2 = nullptr;
17         
18         while(head != nullptr){
19             if(head->val < x){
20                 if(h1 == nullptr){
21                     h1 = l1 = head;
22                 }else{
23                     l1->next = head;
24                     l1 = l1->next;
25                 }
26                 head = head->next;
27                 l1->next = nullptr;
28             }else{
29                 if(h2 == nullptr){
30                     h2 = l2 = head;
31                 }else{
32                     l2->next = head;
33                     l2 = l2->next;
34                 }
35                 head = head->next;
36                 l2->next = nullptr;
37             }
38         }
39         // 2RE here, note that h1 and h2 may be empty!
40         if(h1 == nullptr){
41             return h2;
42         }else if(h2 == nullptr){
43             return h1;
44         }
45         l1->next = h2;
46         head = h1;
47         
48         return head;
49     }
50 };