Partition List

leetcode 86.

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. This problem is a partition problem without knowing the pivot. If it is array, it is this problem.  I firstly use similar way to partition array, the code is a bit over head.

Then I checked this post, it provides a easy implementation. Basically, maintain two lists, less and great, put the element which is less than x to less list, put element which is greater than or equal to x to great list. Isn’t smart?

public static ListNode partition(ListNode head, int x) {
    ListNode less = new ListNode(-1), great = new ListNode(-1), currLess = less, currGreat = great;
    while (head != null) {
        if (head.val < x) {
            currLess.next = head;
            currLess = currLess.next;
        }
        else {
            currGreat.next = head;
            currGreat = currGreat.next;
        }
        head = head.next;
    }
    currLess.next = great.next;
    currGreat.next = null;
    return currLess.next;
}

Check my code on github.