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.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

Solution:

Create a small list and a large list.

Go through the linked list.

If the current node is smaller than x, we link it with the small list.

Otherwise we link the node with the large list.

Finally, we link the small list with the large list.



Code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode small = new ListNode(0);
        ListNode scurr = small;
        ListNode large = new ListNode(0);
        ListNode lcurr = large;
        while (head != null) {
            if (head.val < x) {
                scurr.next = head;
                scurr = scurr.next;
            }
            else {
                lcurr.next = head;
                lcurr = lcurr.next;
            }
            head = head.next;
        }
        lcurr.next = null;
        scurr.next = large.next;
        return small.next;
    }
}