LinkedList

LinkedList删除问题

一般我们给定的LinkedList都是单向链表。所以如果要删除curNode，我们必须知道这个node的 previous node，而在表示curNode的时候，我们不用curNode variable 来 keep track，而是用 prev.next来keep track。从而while loop的退出条件也和prev.next有关。

另外删除操作还有可能带来的问题是head节点可能会被删除，这时我们就需要引入dummy node。

LinkedList reverse问题

所有的reverse问题都是base on基础版的reverse linkedlist I。但是只知道这个还做不了更加 复杂的reverse问题。更复杂的reverse问题需要我们时刻对preM, M, N, postN这四个指针keep track 在认清这四个指针的前提下，每一小段的reverse就和基础版的reverse无差别了。

题目，比如：Swap Nodes in Pairs，Reverse Nodes in k-Group，Reverse Linked List， Reverse Linked List II

Partition/Merge LinkedList问题

Partition:

这些问题的解法对应到array里面就是以前我们partition time O(n), space O(n)的复杂度的 解法：创建两个新的array，然后把partition的结果分别存到对应的array中去。在array问题里面， 我们并不用这样的算法，原因是空间复杂度太高。但是LinkedList并不存在这样的问题，因为 我们永远都是assign reference，而没有创建新的node。所以用了相同的思想，而空间复杂度 却是O(1)。

Merge:

知道这一点之后，我们就可以放心大胆地去应用这套解法了。接下来的问题就变成了创建新链表 的问题。因为是新的链表，我们也需要dummy node，不过他的使用方式和遍历时的dummy node 不一样。在遍历时，我们是dummy = new ListNode(), dummy.next = head。而这里我们并没有 head，所以我们写成dummy = new ListNode(), head = dummy, 然后每次都把新的node append给 head.next ＝ some node。

注意，对于merge sorted lists这个问题，我们的while loop退出条件不需要是or,只需要是&& 就可以了，因为长的list可以直接append到result的结尾。

快慢指针以及找中点问题

一般来说我们找中点时所用的快慢指针slow = head, fast = head.next， 这样fast走到头 慢指针恰好走到中点。如果list长度为偶数，那么慢指针指向的是中间靠左的指针，如果是 奇数，那么指向的是正中间的指针。不过也有特殊情况。对于linkedlist cycle 2，我们最好 还是slow = fast = head，为了满足数学公式。

题目

Reverse

• Leetcode 369. Plus One Linked List
• Leetcode 2. Add Two Numbers
• Leetcode 234. Palindrome Linked List
• Leetcode 206. Reverse Linked List
• Leetcode 92. Reverse Linked List II
• Leetcode 24. Swap Nodes in Pairs
• Leetcode 25. Reverse Nodes in k-Group
• Leetcode 143. Reorder List

Find Middle/双指针

• Leetcode 234. Palindrome Linked List
• Leetcode 19. Remove Nth Node From End of List
• Leetcode 143. Reorder List
• Leetcode 141. Linked List Cycle
• Leetcode 142. Linked List Cycle II
• Leetcode 160. Intersection of Two Linked Lists

Delete

• Leetcode 19. Remove Nth Node From End of List
• Leetcode 83. Remove Duplicates from Sorted List
• Leetcode 82. Remove Duplicates from Sorted List II
• Leetcode 237. Delete Node in a Linked List
• Leetcode 203. Remove Linked List Elements
• Leetcode 147. Insertion Sort List (这道题不是delete,但是用到了prev.next的插入方法)

Partition/Merge

• Leetcode 143. Reorder List
• Leetcode 328. Odd Even Linked List
• Leetcode 21. Merge Two Sorted Lists
• Leetcode 86. Partition List
• Leetcode 148. Sort List

LRU cache

• Lintcode 378. Convert Binary Search Tree to Doubly Linked List