wordpress主題 小工具蘇州seo排名公司
目錄
1.鏈表理論基礎(chǔ)
2.移除鏈表元素
3.設(shè)計(jì)鏈表
4.翻轉(zhuǎn)鏈表
5.兩兩交換鏈表中的節(jié)點(diǎn)
6.刪除鏈表中的第N個(gè)節(jié)點(diǎn)
7.鏈表相交
8.環(huán)形鏈表
1.鏈表理論基礎(chǔ)
鏈表是一種通過指針串聯(lián)在一起的線性結(jié)構(gòu)，每一個(gè)節(jié)點(diǎn)由兩部分組成，一個(gè)是數(shù)據(jù)域一個(gè)是指針域（存放指向下一個(gè)節(jié)點(diǎn)的指針），最后一個(gè)節(jié)點(diǎn)的指針域指向null（空指針的意思）。
鏈表的入口節(jié)點(diǎn)稱為鏈表的頭結(jié)點(diǎn)也就是head。
如下圖所示：
鏈表的類型
單鏈表
也就是剛才所說的
雙鏈表
單鏈表中的指針域只能指向節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)。
雙鏈表：每一個(gè)節(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向下一個(gè)節(jié)點(diǎn)，一個(gè)指向上一個(gè)節(jié)點(diǎn)。
雙鏈表 既可以向前查詢也可以向后查詢。
如圖所示：
循環(huán)鏈表
循環(huán)鏈表，顧名思義，就是鏈表首尾相連。
循環(huán)鏈表可以用來解決約瑟夫環(huán)問題。
鏈表的存儲方式
數(shù)組是在內(nèi)存中是連續(xù)分布的，但是**鏈表在內(nèi)存中不是連續(xù)分布**的。
鏈表是**通過指針域的指針鏈接在內(nèi)存中各個(gè)節(jié)點(diǎn)**。
所以鏈表中的節(jié)點(diǎn)在內(nèi)存中不是連續(xù)分布的 ，而是**散亂分布在內(nèi)存中的某地址上**，分配機(jī)制取決于操作系統(tǒng)的內(nèi)存管理。
如圖所示：
這個(gè)鏈表起始節(jié)點(diǎn)為2， 終止節(jié)點(diǎn)為7，? 各個(gè)節(jié)點(diǎn)分布在內(nèi)存的不同地址空間上，通過指針串聯(lián)在一起。
鏈表的定義
C/C++的定義鏈表節(jié)點(diǎn)方式，如下所示：
struct ListNode {int val;//存儲節(jié)點(diǎn)上面的元素值ListNode* next;//用于指向鏈表的下一個(gè)節(jié)點(diǎn)，初始時(shí)被設(shè)置wULL，表示當(dāng)前節(jié)點(diǎn)是鏈表的末尾ListNode(int x) : val(x),next(NULL) {}//構(gòu)造函數(shù)，初始化ListNode的實(shí)例，接收一個(gè)整型參數(shù)x，并將這個(gè)值賦給當(dāng)前節(jié)點(diǎn)的val成員，//同時(shí)將next指針初始化為NULL，表示這個(gè)節(jié)點(diǎn)后面沒有更多的節(jié)點(diǎn)};
/*操作示例*/
ListNode* head = new ListNode(1);//創(chuàng)建鏈表的頭節(jié)點(diǎn)，值為1
head->next = new ListNode(2);//在頭節(jié)點(diǎn)后面添加一個(gè)新的節(jié)點(diǎn)，值為2有同學(xué)說了，我不定義構(gòu)造函數(shù)行不行，答案是可以的，C++默認(rèn)生成一個(gè)構(gòu)造函數(shù)。
但是這個(gè)構(gòu)造函數(shù)不會初始化任何成員變量，下面我來舉兩個(gè)例子：
通過自己定義構(gòu)造函數(shù)初始化節(jié)點(diǎn)：
ListNode* head = new ListNode(5);使用默認(rèn)構(gòu)造函數(shù)初始化節(jié)點(diǎn)：
ListNode* head = new ListNode();
head->val = 5;所以如果不定義構(gòu)造函數(shù)使用默認(rèn)構(gòu)造函數(shù)的話，在初始化的時(shí)候就不能直接給變量賦值！
鏈表的操作
刪除節(jié)點(diǎn)
刪除D節(jié)點(diǎn)，如圖所示：
只要將C節(jié)點(diǎn)的next指針 指向E節(jié)點(diǎn)就可以了。
那有同學(xué)說了，D節(jié)點(diǎn)不是依然存留在內(nèi)存里么？只不過是沒有在這個(gè)鏈表里而已。
是這樣的，所以在C++里最好是再手動釋放這個(gè)D節(jié)點(diǎn)，釋放這塊內(nèi)存。
其他語言例如Java、Python，就有自己的內(nèi)存回收機(jī)制，就不用自己手動釋放了。
添加節(jié)點(diǎn)
如圖所示：
可以看出鏈表的增添和刪除都是O(1)操作，也不會影響到其他節(jié)點(diǎn)。
但是要注意，要是刪除第五個(gè)節(jié)點(diǎn)，需要從頭節(jié)點(diǎn)查找到第四個(gè)節(jié)點(diǎn)通過next指針進(jìn)行刪除操作，查找的時(shí)間復(fù)雜度是O(n)。
性能分析
把鏈表的特性和數(shù)組的特性進(jìn)行一個(gè)對比，如圖所示：
數(shù)組在定義的時(shí)候，長度就是固定的，如果想改動數(shù)組的長度，就需要重新定義一個(gè)新的數(shù)組。
鏈表的長度可以是不固定的，并且可以動態(tài)增刪， 適合數(shù)據(jù)量不固定，頻繁增刪，較少查詢的場景。
2.移除鏈表元素
題目：
題意：刪除鏈表中等于給定值 val 的所有節(jié)點(diǎn)。
示例 1： 輸入：head = [1,2,6,3,4,5,6], val = 6 輸出：[1,2,3,4,5]
示例 2： 輸入：head = [], val = 1 輸出：[]
示例 3： 輸入：head = [7,7,7,7], val = 7 輸出：[]
思路：
先設(shè)置虛擬頭節(jié)點(diǎn)，因?yàn)榈谝粋€(gè)節(jié)點(diǎn)也有可能是val值，然后移除的操作其實(shí)就是val值的前一個(gè)節(jié)點(diǎn)直接跳過val節(jié)點(diǎn)，指向val的下一個(gè)節(jié)點(diǎn)
注意：跳過的節(jié)點(diǎn)記得手動釋放一下內(nèi)存，節(jié)省空間
代碼如下：
class Solution {
public:ListNode* removeElement(ListNode* head, int val) {ListNode* dummyHead = new ListNode(0);dummyHead->next = head;ListNode* cur = dummyHead;while (cur->val != NULL) {if (cur->next->val == val) {ListNode* tmp = cur->next;cur->next = cur->next->next;delete tmp;}else {cur = cur->next;}}head = dummyHead->next;delete dummyHead;return head;}
};3.設(shè)計(jì)鏈表
題目
a.get(index)：獲取鏈表中第 index 個(gè)節(jié)點(diǎn)的值。如果索引無效，則返回 - 1。
b.addAtHead(val)：在鏈表的第一個(gè)元素之前添加一個(gè)值為 val 的節(jié)點(diǎn)。插入后，新節(jié)點(diǎn)將成為鏈表的第一個(gè)節(jié)點(diǎn)。
c.addAtTail(val)：將值為 val 的節(jié)點(diǎn)追加到鏈表的最后一個(gè)元素。
d.addAtIndex(index, val)：在鏈表中的第 index 個(gè)節(jié)點(diǎn)之前添加值為 val? 的節(jié)點(diǎn)。
如果 index 等于鏈表的長度，則該節(jié)點(diǎn)將附加到鏈表的末尾。如果 index 大于鏈表長度，則不會插入節(jié)點(diǎn)。如果index小于0，則在頭部插入節(jié)點(diǎn)。
e.deleteAtIndex(index)：如果索引 index 有效，則刪除鏈表中的第 index 個(gè)節(jié)點(diǎn)。
注意：
注意初始定義鏈表的狀態(tài)
自己在紙上面寫一遍
注意index的區(qū)間邊界，搞清楚鏈表中的移動大小，以便在正確的位置做插入刪除操作
代碼如下：
class MyLinkedList {
public:struct ListNode {int val;ListNode* next;ListNode(int val) :val(val), next(nullptr) {}};// 初始化鏈表MyLinkedList() {_dummyHead = new ListNode(0); // 這里定義的頭結(jié)點(diǎn) 是一個(gè)虛擬頭結(jié)點(diǎn)，而不是真正的鏈表頭結(jié)點(diǎn)_size = 0;}//a.get(index)：獲取鏈表中第 index 個(gè)節(jié)點(diǎn)的值。如果索引無效，則返回 - 1。int get(int index) {if (index > (_size - 1) || index < 0) {return -1;}else {ListNode* cur = _dummyHead->next;while (index--) {cur = cur->next;}return cur->next->val;}}//b.addAtHead(val)：在鏈表的第一個(gè)元素之前添加一個(gè)值為 val 的節(jié)點(diǎn)。插入后，新節(jié)點(diǎn)將成為鏈表的第一個(gè)節(jié)點(diǎn)。void addAtHead(int val) {ListNode* newNode = new ListNode(val);newNode->next = _dummyHead->next;_dummyHead->next = newNode;_size++;}//c.addAtTail(val)：將值為 val 的節(jié)點(diǎn)追加到鏈表的最后一個(gè)元素。void addAtTail(int val) {ListNode* newNode = new ListNode(val);ListNode* cur = _dummyHead;while (cur->next != NULL) {cur = cur->next;}newNode->next = cur;}
//d.addAtIndex(index, val)：在鏈表中的第 index 個(gè)節(jié)點(diǎn)之前添加值為 val 的節(jié)點(diǎn)。
//如果 index 等于鏈表的長度，則該節(jié)點(diǎn)將附加到鏈表的末尾。如果 index 大于鏈表長度，則不會插入節(jié)點(diǎn)。如果index小于0，則在頭部插入節(jié)點(diǎn)。void addAtIndex(int index, int val) {if (index > _size) return;if (index < 0) index = 0;ListNode* newNode = new ListNode(val);ListNode* cur = _dummyHead;while (index--) {cur = cur->next;}newNode->next = cur->next;cur->next = newNode;_size++;}//e.deleteAtIndex(index)：如果索引 index 有效，則刪除鏈表中的第 index 個(gè)節(jié)點(diǎn)。void deleteAtIndex(int index) {ListNode* cur = _dummyHead;if (index > _size - 1 || index < 0) {return;}while (index--) {cur = cur->next;}ListNode* temp = cur->next;cur->next = cur->next->next;delete temp;temp = NULL;_size--;}//打印鏈表void printLinkedList() {ListNode* cur = _dummyHead;while (cur->next != NULL) {cout << "cur->next-val = " << cur->next->val << endl;cur = cur->next;}cout << endl;}
public:ListNode* _dummyHead;int _size;
};4.翻轉(zhuǎn)鏈表
題目：
題意：反轉(zhuǎn)一個(gè)單鏈表(是將箭頭翻轉(zhuǎn)，不是里面的元素進(jìn)行翻轉(zhuǎn))。
示例: 輸入: 1->2->3->4->5->NULL 輸出: 5->4->3->2->1->NULL
思路：
設(shè)置雙指針法，一個(gè)pre先指向NULL，然后cur在head節(jié)點(diǎn)，不斷更新指向
注意：
使用temp先保存cur->next，因?yàn)橹赶蚋淖兞?#xff0c;不存儲的話無法繼續(xù)進(jìn)行
代碼如下：
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* pre = NULL;ListNode* cur = head;ListNode* temp = new ListNode(0);while (cur) {temp = cur->next;cur->next = pre;//更新pre和curpre = cur;cur = temp;}return pre;}
};5.兩兩交換鏈表中的節(jié)點(diǎn)
題目：
給定一個(gè)鏈表，兩兩交換其中相鄰的節(jié)點(diǎn)，并返回交換后的鏈表。
你不能只是單純的改變節(jié)點(diǎn)內(nèi)部的值，而是需要實(shí)際的進(jìn)行節(jié)點(diǎn)交換。
思路：
按照下圖中的三部進(jìn)行操作即可
注意：
記得保存cur->next與cur->next->next->next的值，因?yàn)橹赶虬l(fā)生了改變
代碼：
class Solution {
public:ListNode* swapPairs(ListNode* head) {ListNode* dummyhead = new ListNode(0);dummyhead->next = head;ListNode* cur = dummyhead;while (cur->next != nullptr && cur->next->next != nullptr) {ListNode* temp = cur->next;ListNode* temp1 = cur->next->next->next;/*dummyhead->next = temp1;temp1->next = temp;temp = cur->next->next->next;*///錯(cuò)誤寫法，不可取cur->next = cur->next->next;cur->next->next = temp;cur->next->next->next = temp1;cur = cur->next->next;}ListNode* result = dummyhead->next;delete dummyhead;return result;}
};6.刪除鏈表中的第N個(gè)節(jié)點(diǎn)
題目：
給你一個(gè)鏈表，刪除鏈表的倒數(shù)第 n 個(gè)結(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎn)。
輸入：head = [1,2,3,4,5], n = 2 輸出：[1,2,3,5]
示例 2：
輸入：head = [1], n = 1 輸出：[]
示例 3：
輸入：head = [1,2], n = 1 輸出：[1]
思路：
使用雙指針法進(jìn)行解決，先定義fast指針和slow指針，初始化為虛擬頭節(jié)點(diǎn)，fast先走n步，然后倆指針一起開始移動，直到fast變?yōu)镹ULL停止，此時(shí)slow指向的正好是刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，這是再改變節(jié)點(diǎn)指向即可
注意：
slow一定要在刪除節(jié)點(diǎn)的前一個(gè)，不然無法繼續(xù)操作
對于while循環(huán)中的邏輯要充足考慮，不要漏掉情況
代碼如下：
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummyhead = new ListNode(0);dummyhead->next = head;ListNode* slow = dummyhead;ListNode* fast = dummyhead;while (n--&&fast->next!=nullptr) {fast = fast->next;}while (fast->next != nullptr) {slow = slow->next;fast = fast->next;}slow->next = slow->next->next;return dummyhead->next;}
};7.鏈表相交
題目：
給你兩個(gè)單鏈表的頭節(jié)點(diǎn) headA 和 headB ，請你找出并返回兩個(gè)單鏈表相交的起始節(jié)點(diǎn)。如果兩個(gè)鏈表沒有交點(diǎn)，返回 null 。
圖示兩個(gè)鏈表在節(jié)點(diǎn) c1 開始相交：
題目數(shù)據(jù) 保證 整個(gè)鏈?zhǔn)浇Y(jié)構(gòu)中不存在環(huán)。
注意，函數(shù)返回結(jié)果后，鏈表必須 **保持其原始結(jié)構(gòu)**
思路：
此時(shí)一定要充分理解鏈表相交，：若兩個(gè)鏈表相交，則兩個(gè)鏈表有共同的節(jié)點(diǎn)，從這個(gè)節(jié)點(diǎn)之后，后面的節(jié)點(diǎn)都會重疊，直到鏈表結(jié)束，若相交，則兩個(gè)鏈表呈現(xiàn)Y字型
?先計(jì)算兩個(gè)列表的長度差值，讓curA和curB這兩個(gè)指針對齊，然后再移動，判斷指針是否相等
如下圖：
注意：
明確鏈表相交是什么
判斷的是指針，不是數(shù)值
代碼：
class Solution {ListNode* listjiao(ListNode* headA, ListNode* headB) {ListNode* curA = headA;ListNode* curB = headB;int sizeA = 0;int sizeB = 0;while (curA != nullptr) {sizeA += 1;curA = curA->next;}while (curB != nullptr) {sizeB += 1;curB = curB->next;}if (sizeB > sizeA) {swap(sizeA, sizeB);swap(headA, headB);}int gap = sizeA - sizeB;while (gap--) {curA = curA->next;}while (curA != nullptr) {if (curA == curB) {return curA;}else {curA = curA->next;curB = curB->next;}}return NULL;}
};
8.環(huán)形鏈表
題目：
題意： 給定一個(gè)鏈表，返回鏈表開始入環(huán)的第一個(gè)節(jié)點(diǎn)。 如果鏈表無環(huán)，則返回 null。
為了表示給定鏈表中的環(huán)，使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該鏈表中沒有環(huán)。
說明：不允許修改給定的鏈表。
思路：
判斷1：鏈表是否有環(huán)
快慢指針法，從頭節(jié)點(diǎn)出發(fā)，fast指針每次移動兩個(gè)節(jié)點(diǎn)，slow指針每次移動一個(gè)節(jié)點(diǎn)，若相遇就是有環(huán)。
判斷2：環(huán)的入口節(jié)點(diǎn)
分別從頭節(jié)點(diǎn)以及相遇節(jié)點(diǎn)出發(fā)一個(gè)指針，每次只走一個(gè)，相遇的時(shí)候就是入口節(jié)點(diǎn)
注意：
最后返回的是環(huán)形入口節(jié)點(diǎn)
代碼：
class Solution {
public:ListNode* detecCycle(ListNode* head) {ListNode* fast = head;ListNode* slow = head;//while (fast->next->next != nullptr && slow != nullptr) {//啰嗦了，可以改一下while(fast!=NULL&&fast->next!=NULL) {fast = fast->next->next;slow = slow->next;//快慢指針相遇if (fast == slow) {ListNode* index1 = head;ListNode* index2 = fast;while (index1 != index2) {index1 = index1->next;index2 = index2->next;}return index1;}}return nullptr;}
};