LeetCode Partition List: Two Pointers and O(1) Space

Overview

LeetCode Partition List Solution: use two pointers with O(1) space to keep the left part (less than x) and right part separately, and concatenate them then.

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.

Solution Analysis: Two Pointers and O(1) Space

Conceptually, there are two lists we need to make, the left list contain the nodes with the value less than the given value, the right list contains the remaining nodes. Ok, then just make four pointers, head and tail pointer to the left list and right list. Linear scan through the list and append those nodes with value less than the given value to the tail of the left list, and append other nodes to the right list, and then concatenate the left and right list together. The following code implement this idea and can be accepted by the LeetCode OJ to pass this Partition List problem:

ListNode *partition(ListNode *head, int x) {
    ListNode l(0);
    ListNode r(0);

    ListNode *lPtr(&l);
    ListNode *rPtr(&r);

    while (head) {
        if (head->val < x) {
            lPtr->next = head;
            lPtr = lPtr->next;
        }
        else {
            rPtr->next = head;
            rPtr = rPtr->next;
        }
        head = head->next;
    }
    lPtr->next = r.next;
    rPtr->next = NULL;
    return l.next;
}

Remarks:

  1. Do not forget to set the tail to NULL for the right part like the 2nd last line of the above code.
  2. Another alternative way would be create another linked list and perform operations similar to merge sort to put the values in the nodes into the other newly created nodes, this avoid using pointers and might be denied say in a job interview
  3. Quick sort partition does not work here because it does not preserve the relative order in each of the two partitions, one test case might be: {2,3,1},  x = 2

Summary

LeetCode Partition List Solution: use two pointers with O(1) space to keep the left part (less than x) and right part separately, and concatenate them then.

Written on May 20, 2013