LeetCode 链表题大集合!

Reverse Linked List
一次扫描翻转链表,设置prev, 很巧妙的方法
Reverse Linked List 2
翻转m 到 n 的节点, 翻转的方法同上,记得记录翻转前的和翻转后结尾的node
Linked List Cycle
耍赖的方法哈希表,O(1) space的方法快慢指针
Linked List Cycle2
耍赖的方法哈希表,O(1) space的方法快慢指针,等它们相遇,在吧期中一个指针放在开头,让它们继续走到相遇
Intersection of Two Linked Lists
耍赖的方法哈希表, 双指针,先扫描一次计算出长度,然后让长的先走一段
Insertion Sort List
链表题的trick之一,dummynode,在不确定head的情况下绝逼好使,注意maintain invairant, 就是sorted和unsorted的界限node, 复杂度O(N^2), Best case, already sorted O(N)
Merge Two Sorted Lists
还是dummyNode
Sort List
用merge sort 用快慢指针找到中间,recursively sort two halves then merge
记得找到中点是吧 next设置为null,不然出现死循环
Remove Duplicates from Sorted List
简单题,注意循环条件 如果不是有序的,用哈希表咯
Remove Duplicates from Sorted List2
上一题的follow up
Partition List
设置两个dummynode, left and right
Rotate List
注意k大于list长度的情况
Reorder List
快慢指针找到Middle,reverse后面的,然后从前面开始编制
Convert Sorted List to Binary Search Tree
让fast先走一步, 快慢指针找到Middle前面的那个一节点,建立root,递归做左右部分,注意next设置为null
Copy List with Random Pointer
1, 用哈希表,扫描两次,以一次记录对应新旧节点的关系,第二次如果有random就可以对应起来了
2, 牛的一比的解法,先复制一次list, 1-2-3 1-1′-2-2′-3-3′ 那么node.next.random = node.random.next
最后在decouple list得到新旧list
Flatten Binary Tree to Linked List
http://www.cnblogs.com/yuzhangcmu/p/4186572.html
http://blog.csdn.net/linhuanmars/article/details/23717703
CC上此题是double linked list

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s