Partition List

Question (LC.86)

Given a singular linked list and a pivot value, partition the list into two parts (< and >=).

Preserve the original relative order of the nodes.

Example

I: 1->4->3->2->5->2, 3
O: 1->2->2->4->3->5

Approach

Create 2 new lists with dummy heads. Then splice them together.

Code

public ListNode partition(ListNode head, int pivot) {
    if (head == null) return null;
    // Step 0 Create two lists    
    ListNode d1 = new ListNode(0), l1 = d1;
    ListNode d2 = new ListNode(0), l2 = d2;
    // Step 1 Partition / Assign nodes
    ListNode travel = head;
    while (travel != null) {
        if (travel.val < pivot) {
            l1.next = travel;
            l1 = l1.next;
        } else {
            l2.next = travel;
            l2 = l2.next;
        }
        travel = travel.next;
    }
    // Step 2 Splice
    l2.next = null;
    l1.next = d2.next;
    return d1.next;
}

Running examples by hand is always important. The result might have a cycle if you don't set l2.next to null.