1. 环形链表的判别 常用于判断链表是否有环的问题，拿可解Leetcode141. Linked List Cycle 举例子，对于如下的链表：
判断是否有环有两种方法：
哈希表。从头开始遍历，若碰见遍历过的节点，就返回“有环”；若碰见未遍历过的节点，就将之加入哈希表；若碰见空指针，就返回“无环”。
从头开始遍历，设立两个指针，一个慢指针指向头节点，一次遍历一个节点，一个快指针指向头节点的下一个节点，一次遍历两个节点，二者若指向同一节点，就返回有环，若二者其中之一碰到空指针，就返回无环。
Java的哈希表更好用一些，第一种方法的Java解法如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 public class Solution { public boolean hasCycle (ListNode head) { HashMap<ListNode, Integer> myMap = new HashMap <>(); while (head != null ) { if (myMap.getOrDefault(head, 0 ) != 0 ) { return true ; } else { myMap.put(head, 1 ); } head = head.next; } return false ; } }
对于快慢指针法，为什么两个指针一定能相遇呢？普遍的环形链表结构如下：
此时，设慢指针走了$x+k$步，那么快指针便走了$2x+2k+1$步(记得算上二者初始差的一步)假设二者无法相遇，则表明：
对于无环链表，显然快慢指针无法相遇。
快慢指针C++解法如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution {public : bool hasCycle (ListNode *head) if (head == nullptr ) return false ; ListNode* slow = head; ListNode* fast = head->next; while (slow != nullptr && fast != nullptr ) { if (slow == fast) { return true ; } slow = slow->next; if (fast->next == nullptr ) return false ; fast = fast->next->next; } return false ; } };
1.5 环形入口的搜索 将上面的$k$解带入$y$快指针走过的距离：
若想让快慢指针相遇在环形入口处，则需要先让快指针走一个节点，然后将慢指针放回头节点，接着让二者向前遍历，相遇点则为环形入口。
可解Leetcode142. Linked List Cycle II ：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution {public : ListNode *detectCycle (ListNode *head) { if (head == nullptr ) return nullptr ; ListNode* slow = head; ListNode* fast = head->next; while (slow != nullptr && fast != nullptr ) { if (slow == fast) { fast = fast->next; slow = head; while (slow != fast) { slow = slow->next; fast = fast->next; } return slow; } slow = slow->next; if (fast->next == nullptr ) return nullptr ; fast = fast->next->next; } return nullptr ; } };
2. 基本的插入/删除/反转/合并问题 在纸上画一画就好，仔细捋清楚节点具体该如何变换、该返回哪个节点、先做什么再做什么。
比如反转链表：Leetcode206. Reverse Linked List ：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution {public : ListNode* reverseList (ListNode* head) { if (head == nullptr ) return nullptr ; ListNode* curr = head; ListNode* prev = nullptr ; ListNode* next = head->next; while (curr != nullptr ) { curr->next = prev; prev = curr; curr = next; next = (next == nullptr ) ? nullptr : next->next; } return prev; } };
此外，利用STL本身的性质解题，往往事半功倍，比如Leetcode23. Merge k Sorted Lists ，利用map底层的红黑树性质解题，速度很快：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution {public : ListNode* mergeKLists (vector<ListNode*>& lists) { ListNode* head = new ListNode (); ListNode* curr = head; map<int , int > dict; for (ListNode* node : lists) { ListNode* temp = node; while (temp != nullptr ) { dict[temp->val]++; temp = temp->next; } } for (auto iter = dict.begin (); iter != dict.end (); ++iter) { int key = iter->first; int val = iter->second; for (int i = 0 ; i < val; ++i) { ListNode* neo = new ListNode (key); curr->next = neo; curr = neo; } } return head->next; } };
2.5 隐藏的成环可能 对于Leetcode143. Reorder List ，完全可以用一个vector记录遍历过的结点，然后根据索引规律排列：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution {public : void reorderList (ListNode* head) vector<ListNode*> memo; ListNode* ptr = head; while (head != nullptr ) { memo.push_back (head); head = head->next; } int l = 0 , r = memo.size () - 1 ; ListNode* curr = ptr; while (l <= r) { if (l == r) { curr->next = memo[l++]; } else { curr->next = memo[l++]; curr = curr->next; curr->next = memo[r--]; curr = curr->next; } } } };
解注释所有注释的语句，可以通过检验。
注释掉的语句的作用是：让遍历到的最后一个节点的下一个节点为空，若不空，则链表会成环，会报类似错误：
==22==ERROR: AddressSanitizer: heap-use-after-free on address 0x6020000000b8 at pc 0x00000038b12d bp 0x7ffda25fd140 sp 0x7ffda25fd138
猜测，可能的原因为，析构ListNode时，是逐个遍历析构的，若成环，则会析构已经析构的节点，报错。
3. 深拷贝问题 所谓深拷贝(deep copy)，就是:
A deep copy of an object is a copy whose properties do not share the same references (point to the same underlying values) as those of the source object from which the copy was made.
一个对象的深拷贝是一种拷贝，其属性值与原对象相等，但是不与原对象共享引用。
——MDN Web Docs
简单来说，就是两个一模一样的对象，分布在不同的内存空间中。本问题对应Leetcode138. Copy List with Random Pointer 。
如果本题链表节点类没有random成员，那么逐个遍历就行。有random，就需要用某种数据结构记忆新旧节点之间的对应关系——哈希表：先复制next关系，将全部节点放置入表；接着复制random关系即可。
一种可行的C++解法如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution {public : Node* copyRandomList (Node* head) { if (head == nullptr ) return nullptr ; map<Node*, Node*> dict; Node* result = new Node (head->val); Node* neo_head = result; Node* memo = head; dict[head] = neo_head; head = head->next; while (head != nullptr ) { Node* curr = new Node (head->val); neo_head->next = curr; neo_head = neo_head->next; dict[head] = neo_head; head = head->next; } head = memo; neo_head = result; while (head != nullptr ) { neo_head->random = dict[head->random]; neo_head = neo_head->next; head = head->next; } return result; } };
递归写法：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public : Node* copyRandomList (Node* head) { if (head == nullptr ) return nullptr ; if (map.count (head)) return map[head]; Node* newNode = new Node (head->val); map[head] = newNode; newNode->next = copyRandomList (head->next); newNode->random = copyRandomList (head->random); return newNode; } private : unordered_map<Node*, Node*> map; };
