❤️[資料結構]動圖詳解連結串列（單連結串列/雙連結串列……）（動圖+範例）【建議收藏】！❤️
🎈 作者：Linux猿
🎈 簡介：CSDN部落格專家🏆，華為雲享專家🏆，C/C++、面試、刷題、演演算法儘管諮詢我，關注我，有問題私聊！
🎈 關注專欄：C/C++面試通關集錦 （優質好文持續更新中……）🚀
目錄
在日常的學習以及求職面試中，連結串列是一塊非常重要的內容，經常被提及，本篇文章總結了連結串列的各種型別，包括：單連結串列、雙連結串列、單項迴圈連結串列、雙向迴圈連結串列、靜態連結串列，接著會有大量真題實戰，想不會都難！趕緊來看下吧！
一、單連結串列
單連結串列是一種最簡單的連結串列形式，每個節點僅有一個指向下一個節點的指標（next 指標），因此，可以將節點連線成一條鏈，如下所示：
通常資料結構為：
struct node {
int data; // 儲存資料
struct node *next; // 指標
};連結串列通常有一個頭節點，比如上圖 Head 所指向的節點，頭節點可以儲存資料，也可以不儲存資料，新增不儲存資料的頭節點通常是為了便於處理連結串列。
1.1 插入節點
單連結串列插入節點有三步：
（1）獲取插入位置前一個節點的指標；
（2）待插入節點的 next 指標指向下一個節點；
（3）前一個節點的 next 指標指向待插入節點；
如下圖所示：
再來看一下動圖：
上述動圖是在節點 2 後面插入節點 9，按照連結串列三步走的方式來，先找到插入節點的位置，然後待插入節點指向下一個節點，前一個節點指向待插入節點。
1.2 刪除結點
單連結串列刪除節點有二步：
（1）獲取刪除節點前一個節點的指標；
（2）前一個節點的指標指向下一個的下一個節點；
如下圖所示：
再來看一下動圖：
二、雙連結串列
雙向連結串列是指每個連結串列節點都有兩個指標，分別指向前後節點，當前節點既可以直接存取下一個節點，也可以直接存取前一個節點。
如下所示：
通常資料結構為：
struct node {
int data; // 儲存資料
struct node *next; // 指向下一個節點
struct node *pre; // 指向前一個節點
};2.1 插入節點
雙連結串列插入節點有二步：
（1）獲取插入位置前一個節點的指標；
（2）待插入節點的 next 指標指向下一個節點，下一個節點的 pre 指標指向待插入節點，前一個節點的 next 指標指向待插入節點，待插入節點 pre 指標指向前一個節點；（實現方法不唯一）
如下圖所示：
再來看一下動圖：
2.2 刪除節點
雙連結串列刪除節點有二步：
（1）獲取刪除節點的指標；
（2）刪除節點前一個節點的 next 指標指向刪除節點的下一個節點，即：node-pre->next = node->next，刪除節點下一個節點的 pre 指標指向刪除節點的前一個節點，即：node->next->pre = node->pre；（實現方法不唯一）
如下圖所示：
再來看一下動圖：
三、單向迴圈連結串列
單向迴圈連結串列將連結串列中的節點相連線，形成了一個環。如下所示：
通常資料結構為：
struct node {
int data; // 資料
struct node *next; // 指標
};資料結構的表示和單連結串列一樣。
3.1 插入節點
單向迴圈連結串列插入節點有三步：
（1）獲取插入位置前一個節點的指標；
（2）待插入節點的 next 指標指向下一個節點；
（3）前一個節點的 next 指標指向待插入節點；
如下圖所示：
再來看一下動圖：
插入節點的方式和單連結串列一樣，但是，單向迴圈連結串列可以從尾指標找到頭指標。
3.2 刪除結點
單向迴圈連結串列刪除節點有二步：
（1）獲取刪除節點前一個節點的指標；
（2）前一個節點的 next 指標指向下一個的下一個節點；
如下圖所示：
再來看一下動圖：
四、雙向迴圈連結串列
雙向迴圈連結串列是指連結串列既有指向下一個節點的 next 指標，又有指向前一個節點的 pre 指標，而且還形成一個雙向環，如下所示：
通常資料結構為：
struct node {
int data; // 儲存資料
struct node *next; // 指向下一個節點
struct node *pre; // 指向前一個節點
};資料結構的表示和雙連結串列一樣。
4.1 插入節點
雙向迴圈連結串列插入節點有二步：
（1）獲取插入位置前一個節點的指標；
（2）待插入節點的 next 指標指向下一個節點，下一個節點的 pre 指標指向待插入節點，前一個節點的 next 指標指向待插入節點，待插入節點 pre 指標指向前一個節點；（實現方法不唯一）
如下圖所示：
再來看一下動圖：
4.2 刪除節點
雙向迴圈連結串列刪除節點有二步：
（1）獲取刪除節點的指標；
（2）刪除節點前一個節點的 next 指標指向刪除節點的下一個節點，即：node-pre->next = node->next，刪除節點下一個節點的 pre 指標指向刪除節點的前一個節點，即：node->next->pre = node->pre；（實現方法不唯一）
如下圖所示：
再來看一下動圖：
五、靜態連結串列
靜態連結串列是結合了順序表和連結串列，通過陣列實現了連結串列。
如下所示：
通常資料結構表示為：
typedef struct {
int data; // 儲存資料
int next; // 陣列下標
}SLink;
SLink g[NUM]; // 陣列六、實戰講解
6.1 連結串列插入排序
6.1.1 題目描述
給定連結串列的頭指標，對給定的連結串列進行插入排序，使得連結串列升序排列。
6.1.2 演演算法思路
使用一個臨時的頭節點 tmpHead，因為如果要進行插入，每次都得從頭開始進行插入。首先，判斷當前節點是否大於等於前一個節點，如果是，則不需要插入，只需要移動節點即可，否則，從 tmpHead 處開始遍歷連結串列，找到一個合適的位置插入當前節點。一直迴圈處理，直到處理完所有節點。
6.1.3 程式碼實現
class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
if(!head) return head; // 空連結串列直接返回
ListNode* tmpHead = new ListNode(0);
tmpHead->next = head;
ListNode* pre = head, *curt, *tmp; // curt 為待排序的節點
while (pre->next) { // pre->next 為待排序的節點
curt = pre->next;
if (pre->val <= curt->val) { // 如果大於或等於前一個節點，則直接移動到下一個節點
pre = pre->next;
continue;
}
tmp = tmpHead; // 從連結串列頭開始遍歷
while (tmp->next->val <= curt->val) { // 尋找大於 curt 的節點
tmp = tmp->next;
}
pre->next = curt->next; // 先刪除 curt 節點
curt->next = tmp->next;
tmp->next = curt;
}
return tmpHead->next; // tmp 僅是臨時使用的
}
};6.1.4 複雜度分析
時間複雜度：O(n^2)，幾乎每次都需要從頭遍歷進行插入元素，連結串列長度為 n，每次遍歷的複雜度為O(n)，故總的時間複雜度為O(n^2)；
空間複雜度：O(1)，這裡僅僅使用到幾個臨時變數，可以忽略，故空間複雜度為O(1)；
6.1.5 題目連結
6.2 合併兩個有序連結串列
6.2.1 題目描述
將兩個升序連結串列合併為一個升序連結串列，新連結串列是通過拼接給定的兩個連結串列的所有節點組成的。
6.2.2 演演算法思路
兩個升序連結串列都是有序的，同時遍歷兩個升序連結串列，每次選取兩個連結串列中值小的節點作為新連結串列的元素，直到所有元素都加入到新連結串列中，和歸併排序中的合併演演算法一樣。如下圖所示：
6.2.3 程式碼實現
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(!l1) return l2; // 一個連結串列為空，直接返回另一個
if(!l2) return l1;
ListNode* Head = new ListNode(0);
ListNode* p = Head;
while (l1 && l2) {
if (l1->val <= l2->val) { // 比較兩個連結串列元素
p->next = l1;
l1 = l1->next;
} else {
p->next = l2;
l2 = l2->next;
}
p = p->next;
}
p->next = l1 ? l1 : l2; // 將沒有合併完了連結串列連結在結尾
return Head->next; // 頭結點沒用到，返回其下一個結點開始的連結串列
}
};6.2.4 複雜度分析
6.2.5 題目連結
6.3 反轉連結串列
6.3.1 題目描述
已知單連結串列的頭節點 head ，請反轉該連結串列，並返回反轉後的連結串列。
6.3.2 演演算法思路
我們拿連結串列中的任意三個連續的節點來舉例（當然，一個或兩個節點也成立），例如：A，B，C，要反轉連結串列，只需執行如下四步即可：
（假設當前節點為 B）
（1）首先，暫存 B 的下一個節點 C；
（2）讓 B->next 指向 A；
（3）當前節點指向 C；
一直重複上面三步，直到所有節點都遍歷完。
6.3.3 程式碼實現
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *pNode = head;
ListNode *tmp = NULL, *pre = NULL; // tmp 用於暫存結點，pre 儲存上一個結點
while(pNode){
tmp = pNode->next; //暫存下一個結點的指標
pNode->next = pre; //當前節點指向前一個節點
pre = pNode; //更新前一個結點
pNode = tmp; //更新當前節點
}
return pre; //返回頭節點
}
};6.3.4 複雜度分析
時間複雜度：O(n)，連結串列長度為 n，程式遍歷一次連結串列，故時間複雜度為 O(n)；
空間複雜度：O(1)，因為沒有用到額外的空間（next 變數可以忽略），故空間複雜度為O(1)；
6.3.5 題目連結
6.4 單連結串列去重
6.4.1 題目描述
給定一個按升序排列的連結串列，連結串列的頭節點為 head ，要求刪除所有重複的元素，使每個元素只出現一次 。
6.4.2 演演算法思路
題目中給出的是升序連結串列，故相同的元素連續在一起，比如：1->2->2->2->5->8->8->10，那麼，去重的時候，只需要用當前節點與下一個節點的值進行比較，如果節點值相等，則讓當前節點的next 指向下一個節點的 next，一直迴圈操作，直到遍歷完所有節點。
6.4.3 程式碼實現
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if(!head) return head;
ListNode* curt = head;
while (curt->next) {
if (curt->val == curt->next->val) { // 與下一個節點比較元素值
curt->next = curt->next->next; // 相等則刪除重複的節點
} else {
curt = curt->next; // 否則向後移動一個元素
}
}
return head; // 返回連結串列頭節點，頭節點沒有變
}
};6.4.4 複雜度分析
時間複雜度：O(n)，連結串列長度為 n，程式中遍歷了一次連結串列，故時間複雜度為O(n)；
空間複雜度：O(1), 程式執行過程中，沒有用到額外的空間，故時間複雜度為O(n)；
注意：有人可能會說，程式中使用到一個臨時變數 curt，這種一個或兩個的空間是相對於 n 是可以忽略的。
6.4.5 題目連結
6.5 判斷連結串列是否有環
6.5.1 題目描述
給定一個連結串列，已知頭節點 head，判斷連結串列中是否有環。
6.5.2 演演算法思路
快慢指標法：
使用兩個指標，慢指標每次移動一步，快指標每次移動兩步，如果存在環，則快指標一定會追上慢指標。
6.5.3 程式碼實現
class Solution {
public:
bool hasCycle(ListNode *head) {
// 排除空連結串列和單個節點的情況
if(head == NULL || head->next == NULL) return false;
ListNode *slow = head, *fast = head->next;
while(slow != fast) {
if(!fast || !fast->next) { // 判斷是否為空
return false;
}
slow = slow->next;
fast = fast->next->next;
}
return true;
}
};6.5.4 複雜度分析
時間複雜度：O(n)；
空間複雜度：O(1)；
6.5.5 題目連結
6.6 刪除連結串列中倒數第 N 個結點
6.6.1 題目描述
給你一個連結串列，刪除所給連結串列的倒數第 n 個結點，並且返回連結串列的頭結點。
6.6.2 演演算法思路
雙指標法：使用兩個指標，first 和 second，讓 first 先移動 n 步，second 指向頭節點，然後，first 和 second 兩個指標同時向後移動，當 first->next 為空的時候，second 指向的節點便是倒數第 n 個節點的前一個節點，這時候就可以刪除倒數第 n 個節點了。
6.6.3 程式碼實現
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) { // 雙指標法
int i = 0;
ListNode* first = head; // 首先，first 指標先移動 n 步
while(i < n && first) {
first = first->next;
i++;
}
if(!first) return head->next; // 如果頭指標是倒數第 n 個，官方資料裡沒有 n 大於連結串列長度的資料
ListNode* second = head;
while(first->next) { // 同時移動 first 和 second 指標
first = first->next;
second = second->next;
}
second->next = second->next->next; // 刪除倒數第 n 個指標
return head;
}
};6.6.4 複雜度分析
時間複雜度：O(n)，只需要遍歷一次連結串列，故時間複雜度為 O(n)；
空間複雜度：O(1)，僅用到兩個指標以及一個變數，是常數級別的，可以忽略，故空間複雜度為O(1)；
6.6.5 題目連結
6.7 移除連結串列中的元素
6.7.1 題目描述
給定一個連結串列的頭節點 head 和一個整數 val ，需要刪除連結串列中所有滿足 node->val == val 的節點。
6.7.2 演演算法思路
設定一個輔助頭節點，依次遍歷元素，如果等於 val 則刪除節點，否則移動到下一個節點。
6.7.3 程式碼實現
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
if(!head) return head;
ListNode* tmpHead = new ListNode(0); // 輔助頭節點
tmpHead->next = head;
ListNode* curt = tmpHead; // 當前節點
while (curt->next) {
if (curt->next->val == val) { // 相等的話刪除
curt->next = curt->next->next;
} else {
curt = curt->next;
}
}
return tmpHead->next;
}
};6.7.4 複雜度分析
6.7.5 題目連結
七、總結
連結串列適合於用在經常作插入和刪除操作的地方，使用的時候注意要判斷連結串列是否為空。
⭐好文推薦⭐
一看就懂！保姆級範例詳解 STL list 容器【萬字整理】
歡迎關注下方👇👇👇公眾號👇👇👇，獲取更多優質內容🤞（比心）！