Course 5: Linked List

1. Remove duplicates from sorted list
2. Remove duplicates from sorted list II
3. Reverse link ed list
4. Reverse linked list II
5. Merge two sorted list
6. Partition list
7. Sort list
8. Reorder list （注意最后要变成null）
9. Remove Nth node from end of list
10. Linked list cycle
11. Linked list cycle II
12. Merge k sorted list
13. Copy list with random pointer
14. Convert sorted list to binary search tree -O(n)

注意:

1. 开始需要判断head==null, head.next==null
2. dummy node
3. Basic skills
   1. Insert a node in sorted list
   2. Remove a node from linked list

public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            re turn null;
        }

        ListNode node = head;
        while (node.next != null) {
            if (node.val == node.next.val) {
                node.next = node.next.next;
            } else {
                node = node.next;
            }
        }
        return head;
    }
}

3. Reverse a linked list

    public ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        }
        return prev;
    }

4. Merger two linked lists

    private ListNode merge(ListNode head1, ListNode head2) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (head1 != null && head2 != null) {
            if (head1.val < head2.val) {
                tail.next = head1;
                head1 = head1.next;
            } else {
                tail.next = head2;
                head2 = head2.next;
            }
            tail = tail.next;
        }
        if (head1 != null) {
            tail.next = head1;
        } else {
            tail.next = head2;
        }

        return dummy.next;
    }

5. Find the middle of a linked list

   private ListNode findMiddle(ListNode head) {
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

4.