Leetcode LinkedList II

第二类的linkedlist 比较复杂，复杂主要是在多种指针的交替赋值变换。要做好这一类题，需要对各个指针的变换有很清晰的概念。比如说删除类交换类的题目，都需要pre指针，往往会构建一个dummy node。

1. swap nodes in pairs.

p作为pre指针，q1, 和q2是要交换的节点。这个清楚了，指针赋值会很容易。最后p=p1，下一个pair的pre指针，

2. reverse nodes in K groups

这道题是非常典型的reverse类型的题。思想是两个指针 pre 和next 中间夹着k个要reverse的nodes。 初始情况下 pre的next 是last， 这个元素最终next指向next。初始情况下last的next是cur，通过不断把新元素加进来，cur不断的后移。cur最终是pre的next。

3.a. Reverse Linked List
Iterative: note the head pointer is passed by reference Recursive: 3.  Reverse Linked List II

Reverse linked list from position m to n.  我们需要找到m-1 和n+1 node 作为 pre 和next，重复2的方法即可

4. Rotate List

重点是找到倒数第k+1个元素。就可以了。需要dummy辅助node

5. Remove duplicated element in sorted Linked List I

思路比较简单，两个指针 pre=NULL 和p=head。 如果两个都不为空且值相等，删除p的节点，p重新指向下一个。否则两个一起前进。

5.1 Remove duplicated element in sorted Linked List II

上题中重复数字需要保留一个因此不需要重复数字之前的pre指针。这道题要求把所有的重复数字都删掉，因此重复数字之前的pre是需要的。

6. Remove element in Linked List 这道题需要将head和其他元素分开考虑

7. Copy List with Random Pointer
这道题需要一个巧妙的解法。 1.把每个node复制一遍，然后把copy插到这个node后面去（A->B 变成 A->A->B->B）然后node->random->next 赋给node->next->random. thats it!

8. LinkList Cycle
思路很简单，一快一慢两个指针，快的每次走两步，慢的走一步。初始他们都指向head。如果他们未来再次相遇，那么就是有cycle

8. LinkList Cycle II
思路不太好想。 需要利用上题结果。当快慢指针相遇的时候，把其中一个重新指向head，然后两个指针同时同速前进，第二次相遇的地方就是cycle起点。 思路的正确性证明参加cc150 2.5. 知道思路之后代码就很容易了

9. Reorder List
用一快一慢指针找到list的中点。把后半部分list reverse。 然后再把前后两部分list merge. 11. LRU Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
为数不多的需要用到双链表的题目。 两个数据结构，一个是hashtable，key是 key， value是key在双链表中的地址。 一个是双链表，用于快速查找key， 快速把最近更新的key放到头部。 双链表需要维护一个tail指针，当满了的时候，需要把tail的元素(least updated)删除。 12. Insertion Sort List: Sort a linked list using insertion sort.
首先一个指针b遍历list，然后一个指针a从头节点遍历到b.如果a>b那么就把b插到a前面。然后b回到原来的位置的后一个。循环。
注意b插a前面需要a的pre指针，记做p.a就是p->next. 把b从原来位置删除也许要前继指针，我们记做pre。 13. Sort List. Sort a linked list in O(n log n) time using constant space complexity.
用归并排序。把list一分为二(用slow和fast指针)，直到子list只有一个或者两个元素。 对他们排序后把两个排好序的子list和在一起。