86. 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.

Example:

Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5
Code
public class Problem86 {

    public class ListNode {

        int      val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    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;

        while (p.next != null) {
            if (p.next.val < x) {
                // Keep adding the lesser values
                p = p.next;
            } else {
                // For the greater than equal to values create a new linked list
                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;
    }

}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s