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.

Understand the problem:
The problem asks for partition a linked list according to a given value x such that all nodes less than x come before nodes greater than or equal to x. 
Also note that the problem asks for the stable partitioning, i.e, preserve the original relative order of the nodes in each of the two partitions. 

We can take several examples to illustrate the problem. 
Given 1 -> 4 -> 3 -> 2 ->5 ->2, and x = 3,
return 1 -> 2 -> 2 -> 3 -> 4 -> 5 (WRONG) See the analysis later

Given 1 -> 2 -> 6 -> 3 -> 2 -> 1, and x = 3
return 1- > 2 -> 2-> 1-> 3 -> 6 (WRONG) See the analysis later

Naive Solution:
Since the problem does not require a in-place partition, one native solution is to scan the linked list once and picked up the nodes less than the pivot. Then append the pivot to the end of the linked list. Finally, scan the list again and append the nodes greater or equal to x.
For this solution, the time complexity is O(n) + O(n) = O(n). The space complexity is O(n) since it is out-of-place partition. 

A better solution:
In the naive solution, we scan the linked list twice and takes additional O(n) space. Can we just scan the list once and take less space? The answer is yes. We scan the list, when the node is less than x, move on and check next. If greater, construct a linked list only storing the greater nodes. If equal, we only need to count the number of nodes that are equal to the target. After we scan the linked list. We only need to append the equal nodes and greater nodes. 

Wrong Code (Java):

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode partition(ListNode head, int x) {
        if (head == null || head.next == null) return head;
        
        // create a helper node to avoid the complexities in updating the head node
        ListNode helper = new ListNode(Integer.MIN_VALUE);
        helper.next = head;
        head = helper;
        
        ListNode p = head;
        
        ListNode head2 = new ListNode(0);
        ListNode p2 = head2;
        int count = 0;
        
        while (p.next != null) {
            if (p.next.val < x) p = p.next;
            else if (p.next.val > x) {
                ListNode temp = p.next;
                p2.next = temp;
                p2 = p2.next;
                p.next = temp.next;
            } else {
                ListNode temp = p.next;
                p.next = temp.next;
                count++;
            }
        }
        p2.next = null;
        
        // append the equal nodes
        for (int i = 0; i < count; i++) {
            ListNode temp = new ListNode(x);
            p.next = temp;
            p = p.next;
        }
        
        // append the greater nodes
        p.next = head2.next;
        
        return head.next;
    }
}

Discussion:
The OJ returned the wrong answer:

Input:	{2,1}, 1
Output:	{1,2}
Expected:	{2,1}

But why? That is because we did not understand the problem correctly. The problem asks for partitioning the list such that all node less than x come before nodes greater OR EQUAL than x. For the example at beginning of the post, 

Given 1 -> 4 -> 3 -> 2 ->5 ->2, and x = 3,
return 1 -> 2 -> 2 -> 3 -> 4 -> 5 (WRONG) 
return 1 -> 2 -> 2 -> 4 -> 3 -> 5 (CORRECT)

Given 1 -> 2 -> 6 -> 3 -> 2 -> 1, and x = 3
return 1- > 2 -> 2-> 1-> 3 -> 6 (WRONG)
return 1 ->2 ->2 -> 1 -> 6 -> 3 (CORRECT)

In the code implementation, we don't need to handle the case where nodes are equal to x, and append the nodes before the nodes greater than x. Then the correct Java code is:

Correct Code (Java):

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode partition(ListNode head, int x) {
        if (head == null || head.next == null) return head;
        
        // create a helper node to avoid the complexities in updating the head node
        ListNode helper = new ListNode(Integer.MIN_VALUE);
        helper.next = head;
        head = helper;
        
        ListNode p = head;
        
        ListNode head2 = new ListNode(0);
        ListNode p2 = head2;
        int count = 0;
        
        while (p.next != null) {
            if (p.next.val < x) p = p.next;
            else {
                ListNode temp = p.next;
                p2.next = temp;
                p2 = p2.next;
                p.next = temp.next;
            }
        }
        p2.next = null;
        
        // append the greater or equal nodes
        p.next = head2.next;
        
        return head.next;
    }
}

Discussion:
Note that in the Line 36 above we must terminate the second list. That is because if not, it may cause a cyclic list. Take an example {3, 1} and x = 2. You will find the cycle. So make sure you understand exactly why we need to terminate the second list. 

This solution has time complexity of O(n) since we only iterate the list once. The space complexity is O(1) as we don't allocate new list to store the second linked list. Note that if we store the second list into another new linked list, there will be no cycle in the linked list and we don't need to handle this problem. But the space complexity becomes O(n) in the worst case. 

Summary:
This problem looks very like the first step of the quick sort. But quick sort is not a stable sorting algorithm. This problem, however, requires a stable partitioning algorithm. Make sure you understand well both the wrong solution and correct solution, as well as the cyclic linked list problem.