86. Partition List

Given a linked list and a valuex, 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,
Given1->4->3->2->5->2andx= 3,
return1->2->2->4->3->5.

思路：用两个指针找到开头，然后连连连。不能忘记释放大的指针的尾部，不然就死循环了

public class Solution {
    public ListNode partition(ListNode head, int x) {
        if (head==null||head.next==null){
            return head;
        }
        ListNode smallerHead = new ListNode(0);
        ListNode small = smallerHead;
        ListNode largerHead = new ListNode(0);
        ListNode large = largerHead;
        ListNode curr = head;
        //search one time
        while (curr!=null){
            if (curr.val<x){
                small.next = curr;
                small = small.next;
            }else{
                large.next = curr;
                large = large.next;
            }
            curr = curr.next;
        }

        //concatenate
        large.next = null; // don't forget to release large.next. This is important
        small.next = largerHead.next;
        return smallerHead.next;
    }
}