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.

Method:

Create two dummy nodes to keep track of the smaller elements and bigger elements.

Solution:

Time: O(n)
Space: O(1)

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     public int val;
 *     public ListNode next;
 *     ListNode(int x) { val = x; next = null; }
 * }
 */
public class Solution {
    public ListNode partition(ListNode A, int B) {
        ListNode dummySmaller = new ListNode(0);
        ListNode dummyBiggerOrEqual = new ListNode(0);
        ListNode pSE = dummySmaller;
        ListNode pB = dummyBiggerOrEqual;
        ListNode curr = A;
        while (curr != null) {
            ListNode next = curr.next;
            if (curr.val < B) {
                pSE.next = curr;
                pSE = pSE.next;
            } else {
                pB.next = curr;
                pB = pB.next;
            }
            curr = next;
        }
        pB.next = null;
        pSE.next = dummyBiggerOrEqual.next;
        return dummySmaller.next;
    }
}