86. Partition List

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.

My Solutions:

• 分成两个head，小的加入small，大的加入big，最后合并

• Time: O(n);

• Space: O(n) 【每次复制node】

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode dummySmall = new ListNode(0);
        ListNode dummyLarge = new ListNode(0);
        ListNode dS = dummySmall; //记录head
        ListNode dL = dummyLarge; //记录head
        
        while (head != null) {
            if (head.val < x) {
                dummySmall.next = head;
                dummySmall = dummySmall.next;
            } else {
                dummyLarge.next = head;
                dummyLarge = dummyLarge.next;
            }
            head = head.next;
        }
        dummySmall.next = dL.next;
        dummyLarge.next = null;    
        return dS.next;    
    }
}