划分链表的第三种解法

这第三中解法和第二种解法有一点类似，都是通过移动节点，一次遍历完成的。区别是第二种解法是将大块向后移动，第三种解法是将小块向前移动。不过，第三种解法比第二种解法更容易理解。

这两种的方法的移动节点的while循环条件有点不一样，可以思考思考。

使用双指针移动节点，虽然有点难，还是有套路的，还是要多写多练。

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param x int整型 
     * @return ListNode类
     */
    public ListNode partition (ListNode head, int x) {
        // write code here
       ListNode dummy=new ListNode(-1);
       ListNode left=dummy;
       left.next=head;
       while(left.next!=null&&left.next.val<x){
           left=left.next;
       }
        ListNode next=left.next;
        ListNode right=next;
        while(right!=null&&right.next!=null){
            if(right.next.val<x){
                left.next=right.next;
                right.next=right.next.next;
                left.next.next=next;
                left=left.next;
            }else{
                right=right.next;
            }
        }
        return dummy.next;
    }
}