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



WA:

1->4->3->2->5->2->null
3

lcur.next = null;
加入后可行， 这个是为了避免产生环

public class Solution {
    /*
     * @param head: The first node of linked list
     * @param x: An integer
     * @return: A ListNode
     */
    public ListNode partition(ListNode head, int x) {
        // write your code here
        ListNode small = new ListNode(-1);
        ListNode scur  = small;
        ListNode large = new ListNode(-1);
        ListNode lcur  = large;
        ListNode dummy = head;
       
        while (dummy != null) {
            if(dummy.val < x){
                scur.next = dummy;
                scur = scur.next;
            } else {
                lcur.next = dummy;
                lcur = lcur.next;
            }
            dummy = dummy.next;
        }
       
        lcur.next = null; // avoid cycle
        scur.next = large.next;
        return small.next;
    }
}