🎈 作者：Linux猿
🎈 簡介：CSDN博客專家🏆，華為云享專家🏆，C/C++、面試、刷題、演算法盡管咨詢我，關注我，有問題私聊！
🎈 關注專欄：C/C++面試通關集錦 （優質好文持續更新中……）🚀
目錄
一、單鏈表
1.1 插入節點
1.2 洗掉結點
二、雙鏈表
2.1 插入節點
2.2 洗掉節點
三、單向回圈鏈表
3.1 插入節點
3.2 洗掉結點
四、雙向回圈鏈表
4.1 插入節點
4.2 洗掉節點
五、靜態鏈表
六、實戰講解
6.1 鏈表插入排序
6.1.1 題目描述
6.1.2 演算法思路
6.1.3 代碼實作
6.1.4 復雜度分析
6.1.5 題目鏈接
6.2 合并兩個有序鏈表
6.2.1 題目描述
6.2.2 演算法思路
6.2.3 代碼實作
6.2.4 復雜度分析
6.2.5 題目鏈接
6.3 反轉鏈表
6.3.1 題目描述
6.3.2 演算法思路
6.3.3 代碼實作
6.3.4 復雜度分析
6.3.5 題目鏈接
6.4 單鏈表去重
6.4.1 題目描述
6.4.2 演算法思路
6.4.3 代碼實作
6.4.4 復雜度分析
6.4.5 題目鏈接
6.5 判斷鏈表是否有環
6.5.1 題目描述
6.5.2 演算法思路
6.5.3 代碼實作
6.5.4 復雜度分析
6.5.5 題目鏈接
6.6 洗掉鏈表中倒數第 N 個結點
6.6.1 題目描述
6.6.2 演算法思路
6.6.3 代碼實作
6.6.4 復雜度分析
6.6.5 題目鏈接
6.7 移除鏈表中的元素
6.7.1 題目描述
6.7.2 演算法思路
6.7.3 代碼實作
6.7.4 復雜度分析
6.7.5 題目鏈接
七、總結
在日常的學習以及求職面試中，鏈表是一塊非常重要的內容，經常被提及，本篇文章總結了鏈表的各種型別，包括：單鏈表、雙鏈表、單項回圈鏈表、雙向回圈鏈表、靜態鏈表，接著會有大量真題實戰，想不會都難！趕緊來看下吧！
一、單鏈表
單鏈表是一種最簡單的鏈表形式，每個節點僅有一個指向下一個節點的指標（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 題目鏈接
力扣
七、總結
鏈表適合于用在經常作插入和洗掉操作的地方，使用的時候注意要判斷鏈表是否為空，
?好文推薦?
保姆級！超詳解！遠程連接Linux虛擬機！
一看就懂！保姆級實體詳解 STL list 容器【萬字整理】
最受歡迎的 Linux 竟然是它，Ubuntu 排第六 ？
歡迎關注下方👇👇👇公眾號👇👇👇，獲取更多優質內容🤞（比心）！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/302237.html
標籤：其他
上一篇：大型企業中如何批量管理千萬臺服務器之ansible自動化運維工具詳解 [?建議收藏?]
下一篇：通信協議定義