Leetcode LinkedList I

Linked List 是比较难的数据结构。不断的变化指针非常容易出错。需要理清思路，切勿硬背。第一类的linkedlist 复杂度稍低，基本都是顺序操作，思路简单，不容易写错。

1. Remove nth node from end  in linkedlist

这道题目思路很简单，主要是定位从后往前数第n个元素，然后把他的前一个的next赋值为他的next即可。注意第一个for循环后 fast-slow=n. 然后两者一起前进直到fast是最后一个元素 此时slow是倒数第n+1个元素 (fast-slow=n) 也就是要删除元素的前一个。

2. Merge two sorted List

这道题并不需要创建新的节点空间，只需要把原有节点next修改即可。辅助dummy node，比较p1 和p2 的第一个元素那个大，地址赋给dummy node的next 然后递增。最后把剩下的接上即可。注意判断空指针


3. Merge K sorted List

这道题List的部分很简单。这道题的主要考点在于heap的用法。思路并不难：把K sorted List想象成k个柱子，最顶上的是最小值。然后从空中俯瞰，是k个最小值。把这k个最小值排入heap，并作以下一些处理： heap的第一个元素（k个最小值里的最小值，也就是全局最小值）加入新建list；pop_heap, 把heap第一个元素所在的柱子放到heap的末尾；再把这根柱子第一个元素弹出，剩下的元素重新组成这个柱子；再把这根柱子push_back回heap。这样每次能保证没跟柱子的最小值中的最小值可以被选走。


4. Partition List

这题如果用对付array的方法做，会很麻烦。比较好的方法是新建一个list，用来存原list中小于x的节点，同时原list将这个节点删去，最后把原list接在新建list上即可。


5. Add two numbers:Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8