一文講透鏈表操作，看完你也能輕鬆寫出正確的鏈表代碼
前言
鏈表和數組一樣，是一種線性的數據結構，算法中的鏈表操作一般都針對單向鏈表，因為單向鏈表比較簡單但是又比較能考研編程者的思維能力。雖然單向鏈表比較簡單，但是要寫好鏈表的代碼也不是一件容易的事，掌握好鏈表有幾個關鍵點：首先就是要防止指針丟失，然後就是我們可以引入哨兵來簡化鏈表的操作，最後巧妙的利用雙指針也可以寫出更高效簡潔的鏈表算法。
什麼是鏈表
鏈表是一種物理存儲單元上非連續、非順序的存儲結構，但是其在邏輯上是連續的。鏈表中每一個數據元素的邏輯順序是通過鏈表中的指針來實現的。
鏈表由一系列結點（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態生成。鏈表的每個結點應至少包括兩個部分：一個是存儲節點的元素信息，另一個是存儲下一個結點地址的 next 指針。
鏈表相比較於數組操作會更複雜一點，而且鏈表和數組也有一些本質區別。
鏈表和數組的區別
鏈表和數組一樣，都是一種線性存儲的數據結構。數組需要內存空間是連續的，所以對內存的要求比較高，因為即使內存中的總剩餘內存足夠，但是假如內存不是連續的，或者說連續的內存空間不夠當前數組的初始化，數組也是無法初始化成功的；而鏈表對內存的要求相對就較低，因為鏈表並不需要內存空間是連續的。除此之外，鏈表和數組在以下的操作中也有本質區別：
- 插入元素
數組中插入元素時，插入位置之後的所有元素都需要往後移動一位，所以數組中插入一個元素最壞時間複雜度是 O(n)，而鏈表卻可以達到 O(1) 的時間複雜度，因為其只需要修改插入位置相關指針的指向即可完成元素的插入。
- 刪除元素
刪除元素也一樣，數組需要將刪除位置之後的元素全部往前移動一位，所以最壞時間複雜度也是 O(n)，而鏈表卻不需要，在鏈表中刪除一個元素也僅僅需要修改相關指針指向即可，時間複雜度為 O(1)。
- 隨機獲取元素
數組因為空間連續，所以隨機獲取一個元素可以達到 O(1) 的時間複雜度，而鏈表卻不行，鏈表隨機獲取一個元素需要從頭節點開始遍歷，所以最壞時間複雜度為 O(n)。
- 獲取長度
數組中獲取長度的時間複雜度是 O(1)，而鏈表只能從頭節點開始遍歷，一直鏈表結尾，所以獲取鏈表長度的時間複雜度也是 O(n)。
常見鏈表類型
在鏈表中，我們通常有三種常見類型：單向鏈表，雙向鏈表和循環鏈表。
單向鏈表
單向鏈表指的是每個節點除了維護自身的節點信息，還會維護一個指向下一個節點的 next 指針，鏈表最後一個節點的 next 指針指向 null，如下圖所示就是一個單向鏈表：
鏈表中第一個節點也被稱之為「頭節點」，頭節點用來記錄鏈表的基地址，一般我們都是通過頭節點去遍歷整條鏈表，直到某一個節點的 next=null，則表示鏈表已經結束，通過遍歷我們就可以得到整條鏈表的長度以及鏈表中的每一個節點。
單向鏈表在算法題中非常受歡迎，因為其操作簡單，但是卻又能考察思維，尤其是鏈表反轉，有序鏈表合併等操作，非常重要，這其中又以鏈表反轉為重中之重，後面我們會專門來分析這兩個問題。
雙向鏈表
相比較於單向鏈表，雙向鏈表多了一個 prev 指針來指向上一個節點，如下圖所示就是一個雙向鏈表：
雙向鏈表在算法中比較少，但是在實際工程中卻應用更加廣泛，比如 Java 的 JUC 當中就大量運用了雙向鏈表，雙向鏈表相比較於單向鏈表也有優勢，比如給定一個節點 Node，要將其從鏈表刪除，那麼這時候如果是單向鏈表只能從頭開始遍歷找到這個節點的前一個節點才能執行刪除操作，而雙向鏈表就不需要，直接通過 prev 指針就能找到當前節點的前一個節點。
循環鏈表
循環鏈表就是首尾相接，比如單向鏈表中，將最後一個節點的 next 指針指向頭節點就形成了一個循環鏈表；在雙向鏈表中將頭節點的 prev 指針指向尾節點，將尾節點的 next 指針指向頭部節點，也形成了一個循環鏈表。
鏈表的基本操作
鏈表的基礎操作同樣的是增刪改查，接下來我們就分別看一下如何對鏈表進行增刪改查操作。
在進行增刪改查之前，我們先初始化一個鏈表：
//定義鏈表節點
public class ListNode {
public int val;//節點中的值
public ListNode next;//指向下一個節點的指針
public int getVal(){
return this.val;
}
ListNode(int x) {
val = x;
next = null;
}
}
//根據數組初始化一個鏈表
package com.lonely.wolf.note.list;
public class ListNodeInit {
public static ListNode initLinkedList(int[] array) {
ListNode head = null, cur = null;
for (int i = 0; i < array.length; i++) {
ListNode newNode = new ListNode(array[i]);
newNode.next = null;
if (i == 0) {//初始化頭節點
head = newNode;
cur = head;
} else {//繼續一個個往後插入節點
cur.next = newNode;
cur = newNode;
}
}
return head;
}
}
獲取鏈表長度
在單向鏈表中，獲取一個鏈表的長度需要從頭節點開始往後遍歷，直到鏈表尾部。所以獲取一個鏈表的長度時間複雜度也是 O(n)：
public static int getListLength(ListNode head){
int length = 0;
while (null != head){
length++;
head = head.next;
}
return length;
}
查找節點
假如說需要查找一個指定節點，或者說查找第 N 個節點，查找方式也是和獲取鏈表長度一樣，從 head 節點開始遍歷，然後進行對比或者計數，直到找到需要的節點，所以查找一個節點的最壞時間複雜度也是 O(n)。
新增節點
假如說我們需要在指定鏈表的指定位置插入一個節點，那麼這時候我們需要考慮以下幾點：
- 當前插入的位置是否超出了鏈表的長度。
- 當前指定的鏈表是否為空。
- 當前插入鏈表的位置是鏈表的頭部，尾部，還是中間位置。
下面就是一個往指定鏈表中指定位置插入一個元素的示例：
public static ListNode insertNode(ListNode head, ListNode insertNode, int position) {
if (null == head){//需要注意當前鏈表為空的情況
return insertNode;
}
int size = ListNodeInit.getListLength(head);//獲取鏈表長度
if (position < 0 || position > size + 1){//處理越界
return head;
}
if (position == 1){//插入頭部（對鏈表一般從 1 開始）
insertNode.next = head;
head = insertNode;
return head;
}
//假如不是插入鏈表頭部，那麼這時候我們需要找到插入位置的前一個節點
ListNode prevNode = head;
int i = 1;
while (i < position-1) {//遍歷到position的前一個節點
prevNode = prevNode.next;
i++;
}
//注意這裡的插入操作，要有器注意指針丟失，如果後面這兩句話反一下，那麼就會造成鏈表斷裂
insertNode.next = prevNode.next;//1
prevNode.next = insertNode;//2
return head;
}
我們以文中開頭的單向鏈表為例子，假如要在第 4 個 位置插入一個 val=5 的節點，這時候我們需要先找到節點 3，也就是上面示例中的 preNode 節點，這時候假如我們先執行上面注釋為 2 的代碼：preNode.next = insertNode，那麼就會出現下圖中情況（虛線的指針表示已經被被改變）：
這時候我們發現原鏈表被斷開，也就是節點 4 已經找不到了，所以插入節點的時候，一定要將新節點和原鏈表先接上才能防止指針丟失。
這裡要劃個重點，請注意鏈表操作一定要謹防指針丟失。
刪除節點
刪除一個節點和插入一個節點類似，也需要考慮各種邊界情況，大家不要以為這些邊界判斷都是小事，事實在面試中寫一個算法，最為重要的就是邊界的判斷，邊界判斷錯誤，可能運行就報錯，運行報錯可能面試就 over 了。
還是以文中開始的單向鏈表為例，假如要刪除節點 3，那麼這時候 pNode 就是 2，deleteNode 就是 3，要把節點 3 刪除的第一步就是把圖中指針 p1 先指向 4，然後再將指針 p2 斷開，即可完成節點的刪除。
下面就是刪除一個節點的示例：
public static ListNode deleteNode(ListNode head,int position) {
if (null == head){//鏈表為空
return null;
}
int length = ListNodeInit.getListLength(head);//獲取鏈表長度
if (position <= 0 || position > length){//刪除位置無效
return head;
}
//刪除頭部節點
ListNode pNode = head;
if (position == 1){
head.next = null;//斷開原head，不斷也行，斷開可以防止內存泄露
return pNode.next;//設置新head
}
int count = 1;
while (count < position - 1){//找到刪除節點的前一個節點
pNode = pNode.next;
count++;
}
//斷開流程見下圖
ListNode deleteNode = pNode.next;//找到需要刪除的節點
pNode.next = deleteNode.next;
deleteNode.next = null;//斷開刪除節點和鏈表的聯繫，不斷也行，斷開可以防止內存泄露
return head;
}
更新節點
如果掌握了前面的查詢，插入，刪除操作，那麼更新就簡單了，如果只是更新節點的 val，那麼遍歷找到節點直接替換即可，如果說要改變某一個節點的位置，那麼可以先刪除原節點，再插入即可完成。
如何寫出 Bug Free 的鏈表代碼
操作鏈表的時候如果想寫出一段 BugFree 的代碼，那麼每次都要至少要反覆考慮下面四種場景下代碼能否正常工作：
- 鏈表為空時，能否達到預期效果。
- 鏈表只有一個
head節點，能否達到預期效果。 - 鏈表只包含兩個節點，能否達到預期效果。
- 如果邏輯處理在頭節點或者尾結點（比如插入和刪除操作），能否達到預期效果。
如果上面四種場景都沒有問題，那麼這段代碼基本上就沒有什麼問題了。
鏈表的重要算法
鏈表的操作非常考驗編程者的思維，一不小心可能就會造成了指針丟失，或者邊界處理錯誤的情況。在掌握了鏈表基本的增刪改查之後，我們繼續來看一下一些稍微複雜點的鏈表操作。
合併有序鏈表
leetcode 中的第 21 題：將兩個升序鏈表合併為一個新的升序鏈表並返回，新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。
這道題不難，在 leetcode 中也是定義為簡單級別，但是這道題的重點是有序列表，而且合併後仍然要保持有序，所以這時候新鏈表的頭節點是誰我們也不知道，如果不使用任何技巧，直接寫也能完成這道題目，但是卻需要做各種判斷，所以這裡我們要介紹另一種技巧，那就是引入哨兵節點。
所謂的哨兵節點，就是定義一個虛擬節點，在這裡我們可以定義一個哨兵節點來作為頭節點，這樣我們只需要在判斷兩個鏈表中元素的大小之後，將元素更小的節點插入哨兵節點的 next 節點即可，然後不斷比較依次插入即可完成，最終返回哨兵節點的 next 節點就是合併後有序鏈表的頭節點。
public static ListNode mergeTwoList(ListNode head1,ListNode head2){
ListNode sentryNode = new ListNode(-1);//哨兵節點
ListNode curr = sentryNode;
while (null != head1 && null != head2){
if (head1.val < head2.val){//如果鏈表1的節點更小，那麼鏈表1往後走
curr.next = head1;
head1 = head1.next;
}else {//如果鏈表2的節點更小，那麼鏈表2往後走
curr.next = head2;
head2 = head2.next;
}
curr = curr.next;
}
//到這裡最多有一個鏈表剩餘節點，也可能都結束了,鏈表的好處就是不需要繼續循環，直接接上剩餘鏈表就行
curr.next = null == head1 ? head2 : head1;//如果兩個都為空，那麼接任意一個都沒關係，都是Null
return sentryNode.next;//返回哨兵節點的下一個節點就是新鏈表的頭節點
}
鏈表反轉
鏈表反轉可以說是操作單向鏈表的精髓，鏈表反轉也是學習鏈表必須要學習的一個功能。
在 leetcode 中，關於鏈表反轉的題目很多，當然，不管題目再多，只要掌握了基礎，那麼其他無非是多繞幾步，比如在指定區間反轉等等。
leetcode 中的第 206 題：給你單鏈表的頭節點 head，請你反轉鏈表，並返回反轉後的鏈表。
這道題的要求很簡單，其中最關鍵的依然是防止指針丟失，我們仍然以文中開始的單向鏈表為例，我們從頭部開始反轉鏈表，那麼首先就需要將下圖中的指針 p1 指向前一個節點，因為當前為頭節點，所以其前一個節點為 null。如果這時候我們上來就直接將指針 p1 指向 null，鏈表就會斷裂，因為鏈表的第二個節點及之後的節點都找不到了，所以在反轉一個節點前，我們必須要記錄好這個節點的下一個節點。
反轉完第一個節點時，這時候開始處理節點 2，那麼依然我們需要先將節點 2 的下一個節點，也就是節點 3 記錄下來：
通過上圖我們又發現問題了，指針 p2 該指向誰呢？很明顯應該是指向節點 1 的，但是這時候我們卻找不到節點 1 了，所以為了能找到節點 1，上面在第一步反轉的時候，我們還需要記錄一個 pre 節點，也就是在每次循環的時候，需要先將當前節點（即下一個反轉節點的 pre 節點）保存下來，這樣才能保證不會斷了聯繫。
做到這兩點之後，我們就可以繼續往後反轉，直到完成整個鏈表的反轉。相關實現代碼如下：
public static ListNode reverseByDirect(ListNode head){
if (null == head || null == head.next){//空或者只有一個節點無需反轉
return head;
}
ListNode pre = null;//記錄前一個節點
ListNode curr = head;//記錄當前反轉的節點
while (null != curr){
ListNode next = curr.next;//記錄下一個節點
curr.next = pre;//將當前節點 next 指向已經反轉的節點
pre = curr;
curr = next;
}
return pre;//最後 pre 就是原鏈表的最後一個節點，也就是新鏈表的頭節點
}
我們在前面實現有序鏈表的合併時提到了哨兵節點的妙用，那麼其實在鏈表反轉中，也可以利用哨兵節點來實現，利用哨兵實現鏈表反轉主要步驟為：
- 定義一個哨兵節點。
- 開始遍歷原鏈表，依次將每個節點插入哨兵之後。注意，每次都是插入哨兵的後面，這樣等全部插入完成之後，哨兵的下一個節點就是原鏈表的最後一個節點。
通過哨兵節點的引入，鏈表的反轉就簡化成了鏈表的插入。相關代碼示例如下：
public static ListNode reverseBySentryNode(ListNode head){
if (null == head || null == head.next){//空或者只有一個節點無需反轉
return head;
}
ListNode sentry = new ListNode(-1);//哨兵節點
ListNode curr = head;
while (null != curr){
ListNode next = curr.next;//記錄下一個節點，防止失聯
curr.next = sentry.next;
sentry.next = curr;//當前節點要接入哨兵之後
curr = next;
}
return sentry.next;
}
尋找倒數第 k 個節點
在劍指 offer 中的第 22 題是尋找鏈表倒數第 k 個節點（鏈表從 1 開始計數），這道題是比較有意思的一道題，正常簡單粗暴的思路就是先遍歷一邊找到鏈表的長度 n，然後第 n-k+1 個節點就是倒數第 k 個節點，這種解法雖然可行，時間複雜度也是 O(n)，但是卻需要遍歷兩次鏈表，那麼能不能通過遍歷一次鏈表實現呢？
在數組當中我們提到了雙指針思想非常重要，其實在鏈表中也一樣，這道題也可以通過快慢指針來快速實現。
我們思考一下，從倒數第 k 個節點走到鏈表的末尾，注意這個末尾指的不是倒數第 1 個節點，而是 null，這時候很明顯需要走 k 步。
知道了這個，那麼就可以利用這個相差 k 步來做文章，我們定義兩個指針，一個 fast，一個 slow。我們首先讓 fast 指針走 k+1 步，然後讓 slow 指針指向 head 節點，這時候 slow 指針和 fast 指針之間是不是也是剛好相差 k 步，那麼這時候再讓 slow 指針和 fast 指針同時走，當 fast 指向鏈表結尾也就是 null 的時候，slow 指針就剛好是倒數第 k 個元素。
相關代碼的實現如下：
public static ListNode findKElementFromEnd(ListNode listNode,int k){
if (k <= 0){
return null;
}
ListNode fast = listNode;
ListNode slow = listNode;
//fast !=null 是為了防止 k 大於鏈表長度的情況
while (fast != null && k > 0) {//fast 指針先走 k 步
fast = fast.next;
k--;
}
while (null != fast){//快慢指針一起走，直到 fast=null
fast = fast.next;
slow = slow.next;
}
return slow;
}
注意這道題裏面，如果 k 大於鏈表長度，那麼會返回頭節點，這是個細節問題，如果面試中碰到，大家最好問清楚如果 k 大於鏈表長度應該如何處理。
總結
本文主要講述了鏈表的基本增刪改查操作，並通過簡單的增刪改查操作，引入了更高級的鏈表合併以及鏈表反轉等算法，最終我們可以得到掌握好鏈表有 3 個關鍵點：首先就是要防止指針丟失，然後就是我們可以引入哨兵來簡化鏈表的操作，最後巧妙的利用雙指針也可以寫出更高效簡潔的鏈表算法。
