[LeetCode] 86. Partition List

Posted on | In

Problem

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.

Example:

1
2
Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5

Explanation

  1. The idea is we iterate each element and move all elements that are less than the target before the index of target, so we need to have a left boundary, in the leftside of this boundary, all elements are less than target. We also needs to have a dummy node before the head (initally left and pre points at dummy node). So, we need to create a left pointer that points at the end of the list of elements that are less than target. We have a cur pointer that is iterating the elements. We also need a pre pointer.

  2. For example, when cur element is less than target, we need to move the cur pointer’s value. So first step, the pre.next = cur.next. Second step, cur.next = left.next because the cur’s next element should be the boundary’s right side which is left.next. And we need to connect the cur to the next element of the left boundary, so third step, left.next = cur. After we move the element that is less than target to the end of the boundary, we need to update left and cur, the pre stay the same because its next element is already connected to the updated cur.

  3. If the element is not less than target, we can just move pre and cur forward one step.

  4. The special case is when left and pre point at the same element. If the current element is not less than target, we normally move pre and cur one step forward. Else, if the current element is less than target, then from the above’s second step cur.next = left.next, in this case, left.next is cur, so after we do the second step, cur is pointing at itself, which is not what we want. To solve this, we can just move left one step forward, pre and cur one step forward.

Solution

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        if (head == null) return head;
        
        ListNode dummy = new ListNode(-1);
        ListNode left = dummy;
        dummy.next = head;
        ListNode pre = dummy;
        ListNode cur = head;
        
        while (cur != null) {
            if (pre == left) {
                if (cur.val < x) left = left.next;
                pre = cur;
                cur = cur.next;
            } else {
                if (cur.val >= x) {
                    pre = cur;
                    cur = cur.next;
                } else {
                    pre.next = cur.next;
                    cur.next = left.next;
                    left.next = cur;
                    
                    left = left.next;
                    cur = pre.next;
                }
            }
        }
        
        return dummy.next;
    }
}