LeetCode Notes002

Albert Chen's Week002

• MergeSortedLists

Solution064

• SortList

Soution148

使用MergeSort，用快慢指针找中间点。
ListNode slow = slow.next;
ListNode fast = fast.next.next;

• MergeKSortedLists 

Solution022

先设定:
最小值min = Integer.Max_VALUE;
最小值所在list序号minList = 0;
已经到结尾的list数目count = 0;

如果某list到了末尾, count++;
每一步比较所有list的head，在循环内将最小的数加入min，并且记录该list的序号在minList

• LinkedListCycle LinkedListCycleII

Solution141
Solution142

http://rockylearningcs.blogspot.com/2014/02/linked-list-cycle-in-leetcode-in-java.html
LinkedListCycle(Solution141): 同上，使用快慢指针；
LinkedListCycleII(Solution142): 有更好的方法是：
(0) isCycle();
(1) 首先找出环的长度（在slow和fast相遇后，让他们继续走，再次相遇的时候，迭代次数就是环的长度C）
(2) 然后让一个指针从链表head开始点先走环的长度C
(3) 再令另一个指针从链表head开始点出发，这样这两个指针的相遇点就必然是交点。因为第一个指针走过了L + C步，第二个指针走过了L步。

• ReverseNodesInKGroup

Solution024
Albert Chen语：大体说来，思路就是取k个，前后标记好，然后把这k个挨个reverse了，然后前后再连好。。。

• CopyListWithRandomPointer

Solution138

Albert Chen语：这题有两种做法。一种是用辅助空间的，就是先把新的node都建好，在旧的node和新的node之间保持一个一一对应关系(比如，用hashmap)，然后把旧的关系拷贝到新的链表上来。这样会占用比较多的空间。

第二种方法如下所示，先为每一个节点建立一个拷贝：

原链表 A->B->C->D
带有拷贝的链表 A->A'->B->B'->C->C'->D->D'

这样为拷贝random pointer提供了一个便利，比如说，A的random pointer指向D，那么我们知道A的next指向A'，D的next指向D'，只要将A的next的random pointer指向D的next就可以了。

最后，NULL要特殊处理，清注意。
可以在Solution138 看到我生成RandomListNode list的函数。