reverse linked list: http://lintcode.com/en/problem/reverse-linked-list/

two pointers: prev, curr
keep a copy of original next for iteration
改变结构
move forward

当需要遍历链表且其结构变化时通常在变化前(usually first step) 记录下original next node for iteration.

注意 return prev 而不是 ~~curr~~

// test case: 1 -> 2 -> 3 -> 4 -> null, return 4 -> 3 -> 2 -> 1 -> null
public ListNode reverse(ListNode node) {

    ListNode prev = null;
    ListNode curr = node;

    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }

    return prev;
}

find middle in linked list

two pointers: fast, slow

fast != null && fast.next != null

// test case 1: 1 -> 2 -> 3 -> 4, return 2
// test case 2: 1 -> 2 -> 3 -> 4 -> 5, return 3
// test case 3: 1, return 1
public ListNode findMiddle(ListNode node) {

    if (node == null) return node;

    ListNode slow = node;
    ListNode fast = node.next;

    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    return slow;    
}

merge two sorted linked list: http://lintcode.com/en/problem/merge-two-sorted-lists/

since need to return original dummy.next, so need a proxy of dummy node which walks through the list. 目的是不影响 dummy的值

i.e. ListNode newNode = dummy;

类似的 curr1, curr2 是 node1, node2 的 proxy

// test case: 1->3->8->11->15->null, 2->null , return 1->2->3->8->11->15->null.
public ListNode merge(ListNode node1, ListNode node2) {

    ListNode curr1 = node1;
    ListNode curr2 = node2;
    ListNode dummy = new ListNode(0);
    ListNode newNode = dummy;

    while (curr1 != null && curr2 != null) {
        if (curr1.val <= curr2.val) {
            newNode.next = curr1; 
            curr1 = curr1.next;
        } else {
            newNode.next = curr2;
            curr2 = curr2.next;
        }
        newNode = newNode.next;    
    }

    if (curr1 == null) {
        dummy.next = curr2;
    }

    if (curr2 == null) {
        dummy.next = curr1;
    }

    return dummy.next;
}

sort list: http://www.lintcode.com/en/problem/sort-list/

find middle
divide and conquer
merge (left, right)

head == null || head.next == null: 终止条件为当前的head为空或者只有一个元素。 i.e. 无法继续分割. 换言之至少有两个元素才能开始后面否则 middle.next 会报错 (1 -> null)

head == null 针对 init input = null

head.next == null 针对有两个元素

middle.next = null: sort left时需要断开链接

Time: O(nlogn), Space: O(n)

// test case 1: 1 -> 3 -> 2, return 1 -> 2 -> 3
// test case 2: 1 -> 5 -> 3 -> 7, return 1 -> 3 -> 5 -> 7
// test case 3: 1, return 1
public ListNode sortList(ListNode head) {

    if (head == null || head.next == null) {
        return head
    }

    ListNode middle = findMiddle(head);
    ListNode right = sortList(middle.next);
    middle.next = null;
    ListNode left = sortList(head);

    return merge(left, right);
}

reorder list: http://www.lintcode.com/en/problem/reorder-list/

find middle
reverse right
merge (left, right)

head == null || head.next == null: 终止条件为当前的head为空或者只有一个元素。 i.e. 无法继续分割. 换言之至少有两个元素才能开始否则 middle.next 会报错 (1 -> null)

middle.next = null: 断开链接

reverse(middle.next): 传到reverse()里的middle.next是一个copy(proxy) 不影响original middle node, so middle.next = null中的middle是original middle

// test case 1: 1 -> 2 -> 3 -> 4, return 1 -> 4 -> 2 -> 3
// test case 2: 1 -> 2 -> 3 -> 4 -> 5, return 1 -> 5 -> 2 -> 4 -> 3
// test case 3: 1 -> null
public ListNode reorderList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }

    ListNode middle = findMiddle(head);
    ListNode right = reverse(middle.next);
    middle.next = null

    return merge(head, right);        
}

reverse linked list ii (m to n reverse): http://www.lintcode.com/en/problem/reverse-linked-list-ii/

find m - 1
reverse (m, n)
handle m - 1, n + 1

need dummy node since head may change

ListNode curr = dummy: need a proxy for dummy since return dummy.next

m <= n

// test case 1: 1 -> 2 -> 3 -> 4 -> 5, m = 2, n = 4, return: 1 -> 4 -> 3 -> 2 -> 5
// test case 2: 1 -> 2 -> 3 -> 4 -> 5, m = 1, n = 2, return: 2 -> 1 -> 3 -> 4 -> 5
public ListNode reverseBetween(ListNode head, int m, int n) {

        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode prev = dummy;
        ListNode curr = head;

        for (int i = 0; i < m-1; i++) {
            prev = curr;
            curr = curr.next;
        }

        ListNode prevStub = prev;

        while (curr != null && m <= n) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr; 
            curr = next;
            m++;
        }

        prevStub.next.next = curr;
        prevStub.next = prev;

        return dummy.next;
}

partition list: http://www.lintcode.com/en/problem/partition-list/

Approach 1: two list (Exceed memory limit, Space O(n), Time O(n))
create dummy left, dummy right to link <=x and >x
merge dummy left

public ListNode partition(ListNode head, int x) {

        ListNode leftDummy = new ListNode(0);
        ListNode rightDummy = new ListNode(0);

        ListNode left = leftDummy;
        ListNode right = rightDummy;

        ListNode curr = head;

        while (curr != null) {
            if (curr.val < x) {
                left.next = curr;
                left = left.next;
            } else {
                right.next = curr;
                right = right.next;
            }

            curr = curr.next;
        }

        left.next = rightDummy.next;

        return leftDummy.next;
    }

Approach 2: in-place (Space: O(n), Time: O(n))
val < x keep the node
else add node to the last
http://yucoding.blogspot.com/2013/04/leetcode-question-63-partition-list.html

remove duplicates from sorted list ii: http://www.lintcode.com/en/problem/remove-duplicates-from-sorted-list-ii/

    public static ListNode deleteDuplicates(ListNode head) {
        // write your code here
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode curr = dummy;

        while (curr.next != null && curr.next.next != null) {

            if (curr.next.val == curr.next.next.val) {
                int val = curr.next.val;
                while (curr.next != null && curr.next.val == val) {
                    curr.next = curr.next.next;
                }
            } else {
                curr = curr.next;
            }
        }

        return dummy.next;
    }

linked list cycle: http://www.lintcode.com/en/problem/linked-list-cycle/

fast-slow pointers

rotated list: http://www.lintcode.com/en/problem/rotate-list/

merge k sorted list (k路归并): http://www.lintcode.com/en/problem/merge-k-sorted-lists/

approach 1: heap
approach 2: divide & conquer
approach 3: merge list 2 by 2
related: merge k sorted arrays, merge 2 sorted list

    // heap
   private Comparator<ListNode> comparator = new Comparator<ListNode>() {
         public int compare(ListNode left, ListNode right) {
             return left.val - right.val;
         }
     };

    public ListNode mergeKLists(List<ListNode> lists) {  
        if (lists == null || lists.size() == 0) return null;

        ListNode dummy = new ListNode(0);
        ListNode curr= dummy;

        Queue<ListNode> heap = new PriorityQueue<>(lists.size(), comparator);

        for (ListNode head : lists) {
            if (head != null)
                heap.add(head);
        }

        while (!heap.isEmpty()) {
            ListNode node = heap.poll();
            curr.next = node;
            curr = curr.next;
            if (node.next != null)
                heap.add(node.next);

        }

        return dummy.next;
    }

    // two by tow merge, divide and conquer 
    public ListNode mergeKLists(List<ListNode> lists) {  
        // write your code here
        if (lists == null || lists.size() == 0) { return null; }

        return mergeHelper(lists, 0, lists.size() - 1);
    }

    private ListNode mergeHelper(List<ListNode> lists, int start, int end) {

        if (start == end) {
            return lists.get(start);
        }

        int mid = start + (end - start) / 2;
        ListNode left = mergeHelper(lists, start, mid);
        ListNode right = mergeHelper(lists, mid + 1, end);

        return merge(left, right);
    }

    private ListNode merge(ListNode left, ListNode right) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        ListNode leftCurr = left;
        ListNode rightCurr = right;

        while (leftCurr != null && rightCurr!= null) {

            if (leftCurr.val < rightCurr.val) {
                curr.next = leftCurr;
                leftCurr = leftCurr.next;
            } else {
                curr.next = rightCurr;
                rightCurr = rightCurr.next;
            }

            curr = curr.next;
        }

        if (leftCurr == null) {
            curr.next = rightCurr;
        }

        if (rightCurr == null) {
            curr.next = leftCurr;
        }

        return dummy.next;
    }

    // merge two by two
    public ListNode mergeKLists(List<ListNode> lists) {  
        // write your code here
        if (lists == null || lists.size() == 0) { return null; }

        while (lists.size() > 1) {

            List<ListNode> mergedList = new ArrayList<>();
            for (int i = 0; i < lists.size() - 1; i += 2) {
                ListNode mergedNode = merge(lists.get(i), lists.get(i+1));
                mergedList.add(mergedNode);
            }

            if (lists.size() % 2 == 1) {
                mergedList.add(lists.get(lists.size() - 1));
            }

            lists = mergedList;
        }

        return lists.get(0);
    }