LintCode - 链表划分（普通）

版权声明：本文为博主原创文章，未经博主允许不得转载。

难度：容易

要求：

给定一个单链表和数值x，划分链表使得所有小于x的节点排在大于等于x的节点之前。你应该保留两部分内链表节点原有的相对顺序。
样例
给定链表 1->4->3->2->5->2->null，并且 x=3返回** 1->2->2->4->3->5->null**

思路：
多指针偏移

/**
     * @param head: The first node of linked list.
     * @param x: an integer
     * @return: a ListNode 
     */
    public ListNode partition(ListNode head, int x) {
        if(head == null){
            return null;
        }
        
        ListNode dummy = new ListNode(0);
        ListNode prev = dummy;
        dummy.next = head;
        ListNode target = null;
        ListNode tmp = null;
        while(prev.next != null){
            if(target == null){
                if(x <= prev.next.val){
                    target = prev.next;
                    tmp = prev.next;
                }else{
                    prev = prev.next;
                }
            }else{
                if(tmp.next == null){
                    break;
                }
                if(tmp.next.val < x){
                    prev.next = tmp.next;
                    prev = prev.next;
                    tmp.next = tmp.next.next;
                }else{
                    tmp = tmp.next;
                }
            }
        }
        
        if(target != null){
            prev.next = target;
        }
        return dummy.next;
    }

思路：
分2个链表,这样思路比较清晰

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 = head;
            } else {
                right.next = head;
                right = head;
            }
            head = head.next;
        }
        
        right.next = null;
        left.next = rightDummy.next;
        return leftDummy.next;
    }