86. Partition List

题目描述

Given a linked list and a valuex, partition it such that all nodes less thanxcome before nodes greater than or equal tox.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given1->4->3->2->5->2andx= 3,
return1->2->2->4->3->5

解题方法

透過兩個dummy node 去做partition (很像merge way)

    public ListNode partition(ListNode head, int x){
        if(head == null){return null;}

        ListNode leftDummy = new ListNode(0);
        ListNode rightDummy = new ListNode(0);
        ListNode left = leftDummy;
        ListNode right = rightDummy;
        while(head != null){
            if(head.val < x){
                left.next = head;
                left = left.next;
            }else{
                right.next = head;
                right = right.next;
            }
            head = head.next;
        }
        right.next = null;              //must be
        left.next = rightDummy.next;
        return leftDummy.next;
    }