連結清單
與數組相似，連結清單也是一種
線性
資料結構。這裡有一個例子：
連結清單中的每個元素實際上是一個單獨的對象，而所有對象都通過每個元素中的引用字段連結在一起。
連結清單有兩種類型：單連結清單和雙連結清單。上面給出的例子是一個單連結清單，這裡有一個雙連結清單的例子：
一 簡介 - 單連結清單
單連結清單中的每個結點不僅包含
值
，還包含連結到下一個結點的
引用字段
。通過這種方式，單連結清單将所有結點按順序組織起來。
1. 結點結構
在大多數情況下，我們将使用頭結點(第一個結點)來表示整個清單。
// Definition for singly-linked list.
struct SinglyListNode {
int val;
SinglyListNode *next;
SinglyListNode(int x) : val(x), next(NULL) {}
};
2. 操作
與數組不同，我們無法在常量時間内通路單連結清單中的随機元素。 如果我們想要獲得第 i 個元素，我們必須從頭結點逐個周遊。 我們按
索引
來
通路元素
平均要花費
O(N)
時間，其中 N 是連結清單的長度。
例如，在上面的示例中，頭結點是 23。通路第 3 個結點的唯一方法是使用頭結點中的“next”字段到達第 2 個結點（結點 6）; 然後使用結點 6 的“next”字段，我們能夠通路第 3 個結點。
你可能想知道為什麼連結清單很有用，盡管它在通過索引通路資料時（與數組相比）具有如此糟糕的性能。 接下來，我們将介紹插入和删除操作，你将了解到連結清單的好處。
2.1 添加操作 - 單連結清單
如果我們想在給定的結點
prev
之後添加新值，我們應該：
- 使用給定值初始化新結點
cur；
單連結清單和雙連結清單 - 将
cur
next
單連結清單和雙連結清單 - 将
prev
cur
單連結清單和雙連結清單
與數組不同，我們不需要将所有元素移動到插入元素之後。是以，您可以在
O(1)
時間複雜度中将新結點插入到連結清單中，這非常高效。
示例
讓我們在第二個結點 6 之後插入一個新的值 9。
我們将首先初始化一個值為 9 的新結點。然後将結點 9 連結到結點 15。最後，将結點 6 連結到結點 9。
插入之後，我們的連結清單将如下所示：
2.2 在開頭添加結點
衆所周知，我們使用頭結點來代表整個清單。
是以，在清單開頭添加新節點時更新頭結點
head
至關重要。
- 初始化一個新結點
cur；
- 将新結點連結到我們的原始頭結點
head
- 将
cur
head
例如，讓我們在清單的開頭添加一個新結點 9。
- 我們初始化一個新結點 9 并将其連結到目前頭結點 23。
單連結清單和雙連結清單 - 指定結點 9 為新的頭結點。
單連結清單和雙連結清單
2.3 删除操作 - 單連結清單
如果我們想從單連結清單中删除現有結點
cur
，可以分兩步完成：
- 找到 cur 的上一個結點
prev
next；
單連結清單和雙連結清單 - 接下來連結
prev
next。
單連結清單和雙連結清單
在我們的第一步中，我們需要找出
prev
和
next
。使用
cur
的參考字段很容易找出
next
，但是，我們必須從頭結點周遊連結清單，以找出
prev
，它的平均時間是
O(N)
，其中 N 是連結清單的長度。是以，删除結點的時間複雜度将是
O(N)
。
空間複雜度為
O(1)
，因為我們隻需要常量空間來存儲指針。
示例
讓我們嘗試把結點 6 從上面的單連結清單中删除。
- 從頭周遊連結清單，直到我們找到前一個結點
prev
- 将
prev
next
結點 6 現在不在我們的單連結清單中。
2.4 删除第一個結點
如果我們想删除第一個結點，政策會有所不同。
正如之前所提到的，我們使用頭結點
head
來表示連結清單。我們的頭是下面示例中的黑色結點 23。
如果想要删除第一個結點，可以簡單地
将下一個結點配置設定給 head
。也就是說，删除之後我們的頭将會是結點 6。
連結清單從頭結點開始，是以結點 23 不再在我們的連結清單中。
3. 連結清單中的雙指針
讓我們從一個經典問題開始：
給定一個連結清單，判斷連結清單中是否有環。
你可能已經使用
哈希表
提出了解決方案。但是，使用
雙指針技巧
有一個更有效的解決方案。
想象一下，有兩個速度不同的跑步者。如果他們在直路上行駛，快跑者将首先到達目的地。但是，如果它們在圓形跑道上跑步，那麼快跑者如果繼續跑步就會追上慢跑者。
這正是我們在連結清單中使用兩個速度不同的指針時會遇到的情況：
-
如果沒有環，快指針将停在連結清單的末尾。
-
如果有環，快指針最終将與慢指針相遇。
是以剩下的問題是：
這兩個指針的适當速度應該是多少？
一個安全的選擇是每次移動慢指針
一步
，而移動快指針
兩步
。每一次疊代，快速指針将額外移動一步。如果環的長度為 M，經過 M 次疊代後，快指針肯定會多繞環一周，并趕上慢指針。
那其他選擇呢？它們有用嗎？它們會更高效嗎？
// Initialize slow & fast pointers
ListNode* slow = head;
ListNode* fast = head;
/**
* Change this condition to fit specific problem.
* Attention: remember to avoid null-pointer error
**/
while (slow && fast && fast->next) {
slow = slow->next; // move slow pointer one step each time
fast = fast->next->next; // move fast pointer two steps each time
if (slow == fast) { // change this condition to fit specific problem
return true;
}
}
return false; // change return value to fit specific problem
提示
它與我們在數組中學到的内容類似。但它可能更棘手而且更容易出錯。你應該注意以下幾點：
1. 在調用 next 字段之前，始終檢查節點是否為空。
擷取空節點的下一個節點将導緻空指針錯誤。例如，在我們運作
fast = fast.next.next
之前，需要檢查
fast
和
fast.next
不為空。
2. 仔細定義循環的結束條件。
運作幾個示例，以確定你的結束條件不會導緻無限循環。在定義結束條件時，你必須考慮我們的第一點提示。
複雜度分析
空間複雜度分析容易。如果隻使用指針，而不使用任何其他額外的空間，那麼空間複雜度将是
O(1)
。但是，時間複雜度的分析比較困難。為了得到答案，我們需要分析
運作循環的次數
。
在前面的查找循環示例中，假設我們每次移動較快的指針 2 步，每次移動較慢的指針 1 步。
- 如果沒有循環，快指針需要
N/2 次
- 如果存在循環，則快指針需要
M 次
顯然，M <= N 。是以我們将循環運作
N
次。對于每次循環，我們隻需要常量級的時間。是以，該算法的時間複雜度總共為
O(N)
。
自己分析其他問題以提高分析能力。别忘了考慮不同的條件。如果很難對所有情況進行分析，考慮最糟糕的情況。
4. 反轉連結清單
讓我們從一個經典問題開始：
反轉一個單連結清單。
一種解決方案是
按原始順序疊代結點
，并将它們
逐個移動到清單的頭部
。似乎很難了解。我們先用一個例子來說明我們的算法。
算法概述
讓我們看一個例子：
請記住，黑色結點 23 是原始的頭結點。
- 首先，我們将黑色結點的下一個結點（即結點 6）移動到清單的頭部：
- 然後，我們将黑色結點的下一個結點（即結點 15）移動到清單的頭部：
- 黑色結點的下一個結點現在是空。是以，我們停止這一過程并傳回新的頭結點 15。
更多
在該算法中，每個結點
隻移動一次
。
是以，時間複雜度為
O(N)
，其中 N 是連結清單的長度。我們隻使用常量級的額外空間，是以空間複雜度為
O(1)。
二 簡介 - 雙連結清單
單連結清單中的結點具有 Value 字段，以及用于順序連結結點的“Next”引用字段。
在本文中，我們将介紹另一種類型的連結清單：
雙連結清單
。
1. 定義
雙連結清單以類似的方式工作，但
還有一個引用字段
，稱為
“prev”
字段。有了這個額外的字段，您就能夠知道目前結點的前一個結點。
讓我們看一個例子：
綠色箭頭表示我們的“prev”字段是如何工作的。
2. 結點結構
下面是雙連結清單中結點結構的典型定義：
// Definition for doubly-linked list.
struct DoublyListNode {
int val;
DoublyListNode *next, *prev;
DoublyListNode(int x) : val(x), next(NULL), prev(NULL) {}
};
與單連結清單類似，我們将使用
頭結點
來表示整個清單。
3. 操作
與單連結清單類似，我們将介紹在雙連結清單中如何通路資料、插入新結點或删除現有結點。
我們可以與單連結清單相同的方式通路資料：
- 我們不能在常量級的時間内
通路随機位置
- 我們必須從頭部周遊才能得到我們想要的第一個結點。
- 在最壞的情況下，時間複雜度将是
O(N)
N
對于添加和删除，會稍微複雜一些，因為我們還需要處理“prev”字段。
3.1 添加操作 - 雙連結清單
如果我們想在現有的結點
prev
之後插入一個新的結點
cur
，我們可以将此過程分為兩個步驟：
- 連結
cur
prev
next
next
prev
單連結清單和雙連結清單 - 用
cur
prev
next
單連結清單和雙連結清單
與單連結清單類似，添加操作的時間和空間複雜度都是
O(1)
。
示例
讓我們在現有結點 6 之後添加一個新結點 9：
- 連結
cur
prev
next
單連結清單和雙連結清單 - 用
cur
prev
next
單連結清單和雙連結清單
3.2 删除操作 - 雙連結清單
如果我們想從雙連結清單中删除一個現有的結點
cur
，我們可以簡單地将它的前一個結點
prev
與下一個結點
next
連結起來。
與單連結清單不同，使用“prev”字段可以很容易地在常量時間内獲得前一個結點。
因為我們不再需要周遊連結清單來擷取前一個結點，是以時間和空間複雜度都是
O(1)
。
示例
我們的目标是從雙連結清單中删除結點 6。
是以，我們将它的前一個結點 23 和下一個結點 15 連結起來：
結點 6 現在不在我們的雙連結清單中。
三 小結 - 連結清單
讓我們簡要回顧一下單連結清單和雙連結清單的表現。
它們在許多操作中是相似的。
- 它們都無法在常量時間内
随機通路資料
- 它們都能夠
在 O(1) 時間内在給定結點之後或清單開頭添加一個新結點
- 它們都能夠
在 O(1) 時間内删除第一個結點
但是删除給定結點(包括最後一個結點)時略有不同。
- 在單連結清單中，它無法擷取給定結點的前一個結點，是以在删除給定結點之前我們必須花費
O(N)
- 在雙連結清單中，這會更容易，因為我們可以使用“prev”引用字段擷取前一個結點。是以我們可以在
O(1)
對照
這裡我們提供連結清單和其他資料結構（包括數組，隊列和棧）之間
時間複雜度
的比較：
經過這次比較，我們不難得出結論：
如果你需要經常添加或删除結點，連結清單可能是一個不錯的選擇。
如果你需要經常按索引通路元素，數組可能是比連結清單更好的選擇。