九章 Linked List

九章 Linked List

1. dummy nodes
  remove duplicates from sorted list
  remove duplicates from sorted list II

scenario: when the head is not determinated
    1. remove duplicates from sorted list I, II
    2. Merge Two sorted Lists
    3. Partition List
    4. Reverse Linked List I, II
    ....

Basic skills
1. insert a node
2. delete a node : a trick ->     a -> b -> c -> d
                               if you already loop at c, you cannot go back
                               you can copy d's value to c, then delete d, 偷梁换柱
3. reverse linked list:  a -> b -> c -> null
                                always keep updating three nodes: prev, cur, next
4. merge two linked list /  merge k sorted list
5. find middle of linked list
(c -> pass by value or pass by reference)
sum(int a)
sum(int* a)
sum(int& a)
sum(const int& a)
6. sort list nlog(n)
 6.1 find mid
  6.2 right = sortlist(mid.next)
   6.3 mid.next = null
   6.4 left = sortlist(head)
    merge(left, right)
7. reorder list
8. linked list circle

9. copy a linked list with next and arbit pointer

10. add two large numbers represented by linked list

11. convert sorted linked list to balance tree