Windows Phone App 8.0 Development (000)

1) Install sdk8.0

2) register windows phone
How to register your phone for development.

3) for the error "Exception from HRESULT: 0x89721500"
Solution: delete the folder "C:\Users\<username>\AppData\Local\Microsoft\Phone Tools\CoreCon\11.0"

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的函数。

第二周主题：链表 之 Linked List Cycle in LeetCode (in java)

题目：

http://oj.leetcode.com/problems/linked-list-cycle/

http://oj.leetcode.com/problems/linked-list-cycle-ii/



要求：
I Given a linked list, determine if it has a cycle in it.


II Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up:
Can you solve it without using extra space?

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

 *     ListNode(int x) : val(x), next(NULL) {}

 * };

 */


(给定一个ListNode结构的链表，(I)看是否有cycle；(II)看循环在哪个节点，如果没有cycle，返回null)




解答：




(I) 设定两个index node: slow and fast，沿着链表的顺序跑下去：slow跑得慢，每次跑一步；fast跑得快，每次跑两步。如果有cycle的话，迟早两个index是会相遇的。




(0) ListNode slow = head; ListNode fast = head;

(1) while (true) 循环内slow = slow.next; fast = fast.next.next; (注意先判断fast.next是否为null)

fast.next == null -> return false;
slow == null -> return false;
fast == null -> return false;
slow == fast -> return true;





(II) 假设找到了cycle (slow == fast)，怎么找是哪个节点开始呢？我们引入一个ListNode pre = head; pre每次跑一步，slow循环一圈找是否slow == pre。那怎么判断slow是否循环一圈呢？别忘了，我们的fast还在那呢，保持fast不动，只要看是否slow == fast就知道了。

(0) slow == fast is true

(1) while (pre != slow) 循环内 slow = slow.next;

slow跑圈 


while ((slow != pre) && (slow != fast)) {
 slow = slow.next;
}

 如果slow跑完了，或者遇到pre了



if (slow == pre)

break;

else

pre = pre.next;




(2) return slow;

References:

[1] 代码在
https://github.com/RockyNiu/LeetCode/blob/master/src/leetcode/java/LinkedListCycle.java
https://github.com/RockyNiu/LeetCode/blob/master/src/leetcode/java/LinkedListCycleII.java