盤點一下面試中最容易被問到的鏈表類算法題，可能下一次面試中就會出現這些題目和技巧哦。
基礎概念
首先，鏈表是一種常見的數據結構，常見的有單鏈表、雙向鏈表等等。 拿單鏈表來舉例，對於每一個節點可以使用下面的數據結構表示：
<code>struct ListNode {
val: any; // 節點的值
next: ListNode; // 該節點指向的下一個節點
}/<code>下圖可以簡單的描述一個鏈表的結構
對於鏈表來說，一定要掌握的操作就是添加節點和刪除節點，因為這是所有技巧的基礎。
刪除節點
如果要在下圖中刪除2這個節點，就可以進行如下操作：
<code>pre.next = cur.next;
cur.next = null;/<code>
因為需要遍歷鏈表找到pre和cur，所以刪除操作的時間複雜度是O(N)，空間複雜度是O(1)
添加節點
如果要在下圖中添加2這個節點，就可以進行如下操作
<code>next = pre.next;
pre.next = cur;
cur.next = next;/<code>
添加新節點的時間複雜度是O(1)，空間複雜度是O(1)
經典題目
反轉鏈表
LeetCode.206，難度簡單
題目
反轉一個單鏈表。
示例:
輸入: 1->2->3->4->5->NULL 輸出: 5->4->3->2->1->NULL
思路
這道題目也算是鏈表類題目的老江湖了，印象中從校招一直考到社招，出現頻率之高令人咋舌。 對於例子1->2->3->4->5->NULL來說，遍歷一遍鏈表，把每個節點的next屬性指向它的前一個節點即可，如下圖所示：
對於每一個節點來說，需要知道它的前一個節點pre是誰，也需要知道它的下一個節點是誰（維持鏈表的遍歷）；下面我給出一個非遞歸的方法，當然也遞歸的方法，讀者感興趣可以自行實現一下。
代碼
<code>/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
if(head === null || head.next === null)
return head;
let pre = null, cur = head;
while(cur !== null) {
const next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
};/<code>
環形鏈表 II
題目
給定一個鏈表，返回鏈表開始入環的第一個節點。 如果鏈表無環，則返回 null。
為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該鏈表中沒有環。
說明：不允許修改給定的鏈表。
示例 1：
輸入：head = [3,2,0,-4], pos = 1 輸出：tail connects to node index 1 解釋：鏈表中有一個環，其尾部連接到第二個節點。
示例 2：
輸入：head = [1,2], pos = 0 輸出：tail connects to node index 0 解釋：鏈表中有一個環，其尾部連接到第一個節點。
示例 3：
輸入：head = [1], pos = -1 輸出：no cycle 解釋：鏈表中沒有環。
思路
這也是一道經典的題目，可以使用快慢指針的辦法來解決之，代碼如下所示； 那麼為什麼使用快慢指針就可以檢測出鏈表是否有環並且找到第一個入環節點呢？證明如下：
如圖，設整個鏈表長度為L，環長度為R，且距離具有方向性，例如CB是C點到B點的距離，BC是B點到C點的距離，CB!=BC。當證明有環時，fast和slow都順時針到了B點，則此時： slow走的距離：AC+CB fast走的距離：AC+k*R+CB(k=0,1,2...) 由於fast每次走2個節點，slow每次走1個節點，所以： 2(AC+CB) = AC+k*R+CB AC+CB = k*R AC+CB = (k-1)*R+R AC = (k-1)*R+R-CB AC = (k-1)*R+BC 從最終的表達式可以看出來，AC的距離等於繞環若干圈後再加上BC的距離，也就是說慢指針從A點出發以速度1前進、快指針從B點出發以速度1前進，則慢指針到C點時，快指針也必然到了。
代碼
<code>/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var detectCycle = function(pHead) {
if(pHead === null || pHead.next === null || pHead.next.next === null)
return null;
var fast = pHead;
var slow = pHead;
while(fast.next !==null && fast.next.next !== null) {
slow = slow.next;
fast = fast.next.next;
if(slow === fast)
break;
}
if(fast === null || fast.next === null || fast.next.next === null)
return null;
// 有環，slow重新回到鏈表頭
slow = pHead;
// slow和fast重新相遇時，相遇節點就是入環節點
while(slow !== fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
};/<code>
奇偶鏈表
LeetCode.328，難度中等
題目
給定一個單鏈表，把所有的奇數節點和偶數節點分別排在一起。請注意，這裡的奇數節點和偶數節點指的是節點編號的奇偶性，而不是節點的值的奇偶性。
請嘗試使用原地算法完成。你的算法的空間複雜度應為 O(1)，時間複雜度應為 O(nodes)，nodes 為節點總數。
示例 1:
輸入: 1->2->3->4->5->NULL 輸出: 1->3->5->2->4->NULL
示例 2:
輸入: 2->1->3->5->6->4->7->NULL 輸出: 2->3->6->7->1->5->4->NULL
說明: 應當保持奇數節點和偶數節點的相對順序。 鏈表的第一個節點視為奇數節點，第二個節點視為偶數節點，以此類推。
思路
之前說過，增刪節點是鏈表的重要基礎技巧，本道題就體現的很深刻。 從題意得知，奇數節點都在前面，偶數節點都在後面，即把1->2->3->4->5->NULL變成1->3->5->2->4->NULL，如下圖所示：
可以看到問題的關鍵是奇數節點和偶數節點交替抽出成兩條獨立的鏈表，最終再合成一條新的鏈表。
代碼
<code>/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var oddEvenList = function(head) {
if(head === null || head.next === null || head.next.next === null)
return head;
let cur1 = head, cur2 = head.next;
let evenHead = head.next;
while(cur1.next && cur2.next) {
cur1.next = cur2.next;
cur1 = cur1.next;
cur2.next = cur1.next;
cur2 = cur2.next;
}
cur1.next = evenHead;
return head;
};/<code>
作者：前端亞古獸
鏈接：https://juejin.im/post/5e8a94a5f265da47fc0cd4c4
閱讀更多 Java技術前沿 的文章
