86. Partition List

My solution is to keep one pointer as the tail of list that is less than x. It also can be interpreted as the position to insert for next element less than x. I forget to deal with a special case where the first element is less than x and got LTE.

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 = new ListNode(-1);  
13:      ListNode *prev = dummy, *cur = head, *par = dummy;  
14:      dummy->next = head;  
15:      while (cur) {  
16:        if (cur->val < x) {  
17:          if (prev == par) {  
18:            cur = cur->next;  
19:            prev = prev->next;  
20:            par = par->next;  
21:          } else {  
22:            prev->next = cur->next;  
23:            cur->next = par->next;  
24:            par->next = cur;  
25:            cur = prev->next;  
26:            par = par->next;  
27:          }  
28:        } else {  
29:          prev = cur;  
30:          cur = cur->next;  
31:        }  
32:      }  
33:      return dummy->next;  
34:    }  
35:  };  

Another solution will be separate the list into two lists and combine them in the end.

When I revisited this problem, I had a bit more concise solution.

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 = new ListNode(-1);  
13:      ListNode *small = dummy;  
14:      ListNode *large = head, *large_head = NULL, *large_prev = NULL;  
15:      while (large) {  
16:        if (large->val < x) {  
17:          small->next = large;  
18:          large = large->next;  
19:          if (large_prev) large_prev->next = large;  
20:          small = small->next;  
21:          small->next = NULL;  
22:        } else {  
23:          if (large_head == NULL) large_head = large;  
24:          large_prev = large;  
25:          large = large->next;  
26:        }  
27:      }  
28:      small->next = large_head;  
29:      head = dummy->next;  
30:      delete dummy;  
31:      return head;  
32:    }  
33:  };