Basic Skills

1. Insert a node in sorted list
2. Remove a node from link list
3. Reverse a linked list

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

Merge two sorted lists

private ListNode interMerge(ListNode head1, ListNode head2){
        ListNode dummy = new ListNode(0);
        ListNode newHead = dummy;
        int i = 0;
        while( head1!= null && head2 != null){
            if((i&1) == 0){
                newHead.next = head1;
                head1 = head1.next;
            }else{
                newHead.next = head2;
                head2 = head2.next;
            }
            newHead = newHead.next;
            i++;
        }
        while(head1 != null){
            newHead.next = head1;
            head1 = head1.next;
            newHead = newHead.next;
        }
        while(head2 != null){
            newHead.next = head2;
            head2 = head2.next;
            newHead = newHead.next;
        }
        return dummy.next;
    }

find the middle of a linked list

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

解题方法

a. Merge Sort

1. 找中點 <--fast/slow pointer

2. 拆分

3. sort

4. Merge

b. 檢查boundary

head != null, head.next != null

while(head.next != null)

c. 保留 Cur/Pre node

pre, current node

d. Dummy node <-注意head node

考點

1. delete duplicate nodes / delete all duplicate nodes <---dummy node
2. Reverse LinkedList <----all reverse / partial reverse <---previous node
3. partition list (透過dummpy left, right 派分) / partition array
4. Merge sorted K list (Priority queue)
5. Clone (deep clone) : O(n) hash map // O(1) 遍歷/clone random/partition (used two dummy)
6. Rotated list