柚子快報(bào)激活碼778899分享：數(shù)據(jù)結(jié)構(gòu) 【基礎(chǔ)算法總結(jié)】鏈表

http://yzkb.51969.com/

鏈表

1.鏈表常用技巧和操作總結(jié)2.兩數(shù)相加4.兩兩交換鏈表中的節(jié)點(diǎn)4.重排鏈表5.合并 K 個(gè)升序鏈表6.K 個(gè)一組翻轉(zhuǎn)鏈表

點(diǎn)贊??收藏??關(guān)注?? 你的支持是對(duì)我最大的鼓勵(lì)，我們一起努力吧!??

1.鏈表常用技巧和操作總結(jié)

常用技巧

1.畫(huà)圖 !!! -> 直觀 + 形象 + 便于我們理解

2.引入虛擬 “頭” 節(jié)點(diǎn)

便于處理邊界情況方便我們對(duì)鏈表操作

3.不要吝嗇空間，大膽去定義變量

比如都會(huì)遇到到這種題，前兩句必須放前面，不然鏈表就斷開(kāi)了。但是我們可以定義一個(gè)next，這樣就不用管按什么順序了。

4.快慢指針

判環(huán)，找鏈表中環(huán)的入口，找鏈表中倒數(shù)第 n 個(gè)節(jié)點(diǎn)，都是用快慢指針解決的。

鏈表中的常用操作

1.創(chuàng)建一個(gè)新節(jié)點(diǎn) new

2.尾插

3.頭插

2.兩數(shù)相加

題目鏈接：2. 兩數(shù)相加

題目分析：

給兩個(gè)鏈表，注意是逆序的。將兩個(gè)數(shù)相加，還以逆序方式返回一個(gè)表示和的鏈表。

這道題給逆序正好方便我們從低位相加，如果是正序給的還要把鏈表逆置一下。 算法原理：

解法：模擬兩數(shù)相加的過(guò)程即可

我們先來(lái)一個(gè)虛擬頭結(jié)點(diǎn)，這樣就少了判斷為空的情況，直接尾插即可！在來(lái)一個(gè) t 表示進(jìn)位。t = cur1->val + cur2->val，每次都拿個(gè)數(shù)位構(gòu)建節(jié)點(diǎn)。

class Solution {

public:

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

ListNode* newhead, *tail;

newhead = tail = new ListNode;//創(chuàng)建一個(gè)虛擬節(jié)點(diǎn)記錄最終結(jié)果

ListNode* cur1 = l1, *cur2 = l2;

int t = 0; // 記錄進(jìn)位

while(cur1 || cur2 || t)

{

// 先加上第一個(gè)鏈表

if(cur1)

{

t += cur1->val;

cur1 = cur1->next;

}

// 加上第二個(gè)鏈表

if(cur2)

{

t += cur2->val;

cur2 = cur2->next;

}

tail->next = new ListNode(t % 10);

tail = tail->next;

t /= 10;

}

//防內(nèi)存泄漏

// tail = newhead->next;

// delete newhead;

// return tail;

return newhead->next;

}

};

4.兩兩交換鏈表中的節(jié)點(diǎn)

題目鏈接：24. 兩兩交換鏈表中的節(jié)點(diǎn)

題目分析：

兩兩交換鏈表的節(jié)點(diǎn)，注意不能直接交換里面的值，只能修改指針。這道題在遞歸、搜索回溯專(zhuān)題用遞歸的方法解決。這里用循環(huán)迭代的方式。

算法原理：

解法一：遞歸

解法二：循環(huán)、迭代(模擬)

引入一個(gè)頭節(jié)點(diǎn)，這樣就減少判斷邊界的問(wèn)題。如果不引入，交換前兩個(gè)節(jié)點(diǎn)和后面的節(jié)點(diǎn)寫(xiě)法是不一樣的，因?yàn)檫€要返回頭指針，所以就只能先處理前兩個(gè)找到最終返回的頭節(jié)點(diǎn)，然后在處理后面的。這樣太麻煩了。引入頭節(jié)點(diǎn)，因?yàn)橐呀?jīng)有了頭節(jié)點(diǎn)所有后面處理邏輯都是一樣的。

因?yàn)槲覀円獌蓛山粨Q，這里我們需要四個(gè)指針。不要吝嗇空間，大膽去定義變量 ，這樣交換指針的時(shí)候，不用擔(dān)心代碼順序?qū)е抡也坏芥湵淼膯?wèn)題，有了這四個(gè)指針隨便先寫(xiě)那一步。交換之后指針都移動(dòng)一下。

什么時(shí)候結(jié)束呢？節(jié)點(diǎn)可能有奇數(shù)個(gè)，也可能有偶數(shù)個(gè)。

可以看到當(dāng)cur或者next為空的時(shí)候就結(jié)束了。

class Solution {

public:

ListNode* swapPairs(ListNode* head) {

if(head == nullptr || head->next == nullptr) return head;

ListNode* newhead = new ListNode;

newhead->next = head;

ListNode* prev = newhead, *cur = head, *next = head->next, *nnext = head->next->next;

while(cur && next)

{

// 交換節(jié)點(diǎn)

prev->next = next;

next->next = cur;

cur->next = nnext;

// 修改指針，注意nullptr指針解引用

prev = cur;

cur = nnext;

if(cur) next = cur->next;

if(next)nnext = next->next;

}

return newhead->next;

}

};

4.重排鏈表

題目鏈接：143. 重排鏈表

題目分析：

給一個(gè)鏈表讓按照規(guī)則重排一下。

算法原理：

解法：模擬

找到鏈表的中間節(jié)點(diǎn) 快慢指針把后面的部分逆序 頭插合并兩個(gè)鏈表 (合并兩個(gè)有序鏈表)雙指針

對(duì)于找到中間節(jié)點(diǎn)然后逆序，有兩種做法。

第一種逆序策略：slow->next 后面逆序

因?yàn)檫@道題比較特殊可以將slow->next 后面逆序，因?yàn)槟銜?huì)發(fā)現(xiàn)逆序完之后中間位置還是在一起的。因此可以大膽將slow節(jié)點(diǎn)給第一個(gè)鏈表。

第二種逆序策略：從slow位置開(kāi)始逆序

兩種策略都是可以的。

但是如果使用頭插法逆序，建議還是第一種策略，因?yàn)槲覀兪窍胱寖蓚€(gè)鏈表斷開(kāi)的。如果想逆序后鏈表還是在一起的，就用第二種策略。

第一種策略

class Solution

{

public:

void reorderList(ListNode* head)

{

// 處理邊界情況

if(head == nullptr || head->next == nullptr || head->next->next == nullp

// 1. 找到鏈表的中間節(jié)點(diǎn) - 快慢雙指針（?定要畫(huà)圖考慮 slow 的落點(diǎn)在哪?）

ListNode* slow = head, *fast = head;

while(fast && fast->next)

{

slow = slow->next;

fast = fast->next->next;

}

// 2. 把 slow 后?的部分給逆序 - 頭插法

ListNode* head2 = new ListNode(0);

ListNode* cur = slow->next;

slow->next = nullptr; // 注意把兩個(gè)鏈表給斷開(kāi)

while(cur)

{

ListNode* next = cur->next;

cur->next = head2->next;

head2->next = cur;

cur = next;

}

// 3. 合并兩個(gè)鏈表 - 雙指針

ListNode* ret = new ListNode(0);

ListNode* prev = ret;

ListNode* cur1 = head, *cur2 = head2->next;

while(cur1)

{

// 先放第?個(gè)鏈表

prev->next = cur1;

cur1 = cur1->next;

prev = prev->next;

// 再放第?個(gè)鏈表

if(cur2)

{

prev->next = cur2;

prev = prev->next;

cur2 = cur2->next;

}

}

delete head2;

delete ret;

}

};

第二種策略

class Solution {

public:

void reorderList(ListNode* head) {

// 處理邊界情況

if(head == nullptr || head->next == nullptr || head->next->next == nullptr) return;

// 1.找鏈表中間節(jié)點(diǎn) -> 快慢指針(畫(huà)圖考慮slow的落點(diǎn)在哪里)

ListNode* fast = head, *slow = head;

while(fast && fast->next)

{

slow = slow->next;

fast = fast->next->next;

}

// 2.將slow以及后面鏈表翻轉(zhuǎn) -> 頭插法

ListNode *cur = slow, *phead = nullptr, *next = nullptr;

while(cur)

{

next = cur->next;

cur->next = phead;

phead = cur;

cur = next;

}

// 3.合并兩個(gè)鏈表 -> 雙指針

ListNode* newhead = nullptr, *tail = nullptr;

newhead = tail = new ListNode(0);

int i = 1;

while(phead)

{

if(i%2 != 0)

{

tail->next = head;

tail = head;

head = head->next;

}

else

{

tail->next = phead;

tail = phead;

phead = phead->next;

}

++i;

}

head = newhead->next;

delete newhead;

}

};

5.合并 K 個(gè)升序鏈表

題目鏈接： 23. 合并 K 個(gè)升序鏈表

題目分析：

前面學(xué)過(guò)合并兩個(gè)有序鏈表，現(xiàn)在有k個(gè)有序鏈表讓合并一下。

算法原理：

解法一：暴力求解 利用合并兩個(gè)有序鏈表思想，可以先讓前兩個(gè)鏈表合并成一個(gè)新的鏈表，然后拿新的鏈表在和下一個(gè)鏈表合并。。。。直到把所有鏈表合并完。

但是時(shí)間復(fù)雜度很恐怖，假設(shè)每一個(gè)鏈表長(zhǎng)度為n，共有k個(gè)鏈表?？春喜状斡行蜴湵?。如果是第一個(gè)鏈表，需要合并k-1次，并且長(zhǎng)度為n，所以第一個(gè)鏈表 時(shí)間復(fù)雜度 n(k-1)。第二個(gè)鏈表n(k-2)。。。所以最終時(shí)間復(fù)雜度為O(nk^2)

解法二：利用優(yōu)先級(jí)隊(duì)列做優(yōu)化

合并K個(gè)有序鏈表，我們可以仿照合并兩個(gè)有序鏈表的邏輯。先不考慮優(yōu)先級(jí)隊(duì)列，考慮如何對(duì)上面的做優(yōu)化。

我們仿照合并兩個(gè)有序鏈表的邏輯，先定義K個(gè)指針指向每一個(gè)鏈表，找出這個(gè)K個(gè)指針中值較小的節(jié)點(diǎn)，放在newhead的后面，放完之后，讓這個(gè)指針往后移動(dòng)。然后繼續(xù)比較這K個(gè)指針指向的節(jié)點(diǎn)。這正好就是合并兩個(gè)有序鏈表的邏輯。K個(gè)鏈表就K個(gè)指針，誰(shuí)小誰(shuí)就先連接newhead后面。

如何快速找到誰(shuí)是K個(gè)節(jié)點(diǎn)中誰(shuí)是較小的那個(gè)呢？ 利用優(yōu)先級(jí)隊(duì)列。

因此我們的最終策略就是，搞一個(gè)小根堆，先將K個(gè)指針先丟到小根堆里，堆頂放的節(jié)點(diǎn)就是接下來(lái)我們要連接到newhead后面的節(jié)點(diǎn)。將堆頂節(jié)點(diǎn)連接到newhead后面之后，讓這個(gè)指針往后移動(dòng)然后進(jìn)入優(yōu)先級(jí)隊(duì)列。此時(shí)堆頂也還是K個(gè)指針中最小的節(jié)點(diǎn)。。。。直到指針到空就不讓這個(gè)鏈表進(jìn)入隊(duì)列了。等到所有鏈表的指針都到空了。說(shuō)明鏈表合并結(jié)束了。

堆每次調(diào)整logk，一共進(jìn)入nk個(gè)，所以這個(gè)時(shí)間復(fù)雜度O(nklogk)

class Solution

{

public:

//類(lèi)中的仿函數(shù)不能支持我們將最小節(jié)點(diǎn)放在棧頂

//因此指針并不是遞增

//所以自己定義一個(gè)仿函數(shù)用來(lái)支持將最小節(jié)點(diǎn)放在棧頂

struct greater

{

bool operator()(const ListNode* x,const ListNode* y)

{

return x->val > y->val;

}

};

ListNode* mergeKLists(vector& lists)

{

if(lists.empty()) return nullptr;

ListNode* newhead = new ListNode;

ListNode* tail = newhead;

priority_queue,greater> pq;

for(int i = 0; i < lists.size(); ++i)

{

if(lists[i])

pq.push(lists[i]);

}

while(!pq.empty())

{

// 出

ListNode* cur = pq.top();

tail->next = cur;

tail = cur;

pq.pop();

//進(jìn)

if(cur->next)

pq.push(cur->next);

}

return newhead->next;

}

};

解法三：分治 - 遞歸 利用歸并排序。

假設(shè)有6個(gè)鏈表，讓把這6個(gè)合起來(lái)成一個(gè)有序鏈表。此時(shí)可以沿著中間將6個(gè)鏈表一分為二，左邊三個(gè)鏈表，右邊三個(gè)鏈表，現(xiàn)讓左邊三個(gè)合并成一個(gè)鏈表，然后在讓右邊三個(gè)合并成一個(gè)鏈表。然后拿著這個(gè)兩個(gè)有序鏈表，在合并成一個(gè)有序鏈表。

兩個(gè)有序鏈表，在合并成一個(gè)有序鏈表。我們是非常熟悉的。

現(xiàn)在重點(diǎn)就是上面的讓左邊三個(gè)合并成一個(gè)，右邊三個(gè)合并成一個(gè)，應(yīng)該怎么做呢？

其實(shí)是和這個(gè)大過(guò)程是一樣的。以左邊三個(gè)為例，策略和上面一樣。把三個(gè)鏈表從中間分開(kāi)。先左邊一個(gè)合并成一個(gè)有序鏈表，在讓右邊兩個(gè)合并成一個(gè)有序鏈表。然后在把這兩個(gè)鏈表合并成一個(gè)有序鏈表。左右可以再分。邏輯是一模一樣的，這整體就是一個(gè)遞歸過(guò)程！

此時(shí)我們就可以用遞歸來(lái)實(shí)現(xiàn)這個(gè)策略。并且和歸并排序過(guò)程是一樣的。

歸并排序先分然后才合，時(shí)間復(fù)雜度我們緊盯每一個(gè)鏈表節(jié)點(diǎn)執(zhí)行多少次。分就是一個(gè)完全二叉樹(shù)。每一個(gè)鏈表都會(huì)合并，合并次數(shù)是這個(gè)數(shù)的高度次，假設(shè)有k個(gè)鏈表樹(shù)高度logk，每一個(gè)鏈表都執(zhí)行l(wèi)ogk合并，一共有k個(gè)鏈表，每一個(gè)鏈表有n個(gè)節(jié)點(diǎn)，所以時(shí)間復(fù)雜度O(nklogk)

class Solution

{

public:

ListNode* mergeKLists(vector& lists)

{

return MergeSort(lists, 0, lists.size() - 1);

}

ListNode* MergeSort(vector& lists, int left, int right)

{

if(left > right) return nullptr;

if(left == right) return lists[left];

int mid = left + (right - left) / 2;

ListNode* newhead1 = MergeSort(lists, left, mid);

ListNode* newhead2 = MergeSort(lists, mid + 1, right);

ListNode* newhead = new ListNode;

ListNode* tail = newhead;

ListNode* cur1 = newhead1, *cur2 = newhead2;

while(cur1 && cur2)

{

if(cur1->val < cur2->val)

{

tail->next = cur1;

tail = cur1;

cur1 = cur1->next;

}

else

{

tail->next = cur2;

tail = cur2;

cur2 = cur2->next;

}

}

if(cur1)

tail->next = cur1;

if(cur2)

tail->next = cur2;

tail = newhead->next;

delete newhead;

return tail;

}

};

6.K 個(gè)一組翻轉(zhuǎn)鏈表

題目鏈接：25. K 個(gè)一組翻轉(zhuǎn)鏈表

題目分析：

前面有一道題是兩兩一組翻轉(zhuǎn)鏈表，現(xiàn)在是讓k個(gè)一組翻轉(zhuǎn)鏈表，小于k的就不用翻轉(zhuǎn)了。

算法原理：

解法：模擬

先求出需要逆序多少組： n重復(fù) n 次，長(zhǎng)度為 k 的鏈表的逆序即可(頭插法)

先求出需要逆序多少組： n，剩下的就不逆序了，直接連接上就好了。申請(qǐng)一個(gè)頭結(jié)點(diǎn)newhead，把k個(gè)節(jié)點(diǎn)頭插到newhead后面即可。注意這只是第一組，下一組也要頭插怎么辦？因此我們需要一個(gè)tmp指針記錄下一次執(zhí)行頭插的頭結(jié)點(diǎn)在哪，prev在一次頭插結(jié)束之后就更新一下 prev = tmp ，prev指向充當(dāng)頭結(jié)點(diǎn)。

class Solution {

public:

ListNode* reverseKGroup(ListNode* head, int k) {

// 1.先求出需要逆序多少組

int n = 0;

ListNode* cur = head;

while(cur)

{

++n;

cur = cur->next;

}

n /= k;

// 2.重復(fù) n 次: 長(zhǎng)度為 k 的鏈表逆序即可

ListNode* newhead = new ListNode;

ListNode* prev = newhead;

cur = head;

for(int i = 0; i < n; ++i)

{

ListNode* tmp = cur;

for(int j = 0; j < k; ++j)

{

ListNode* next = cur->next;

cur->next = prev->next;

prev->next = cur;

cur = next;

}

prev = tmp;

}

// 3.把不需要翻轉(zhuǎn)的接上

prev->next = cur;

prev = newhead->next;

delete newhead;

return prev;

}

};

柚子快報(bào)激活碼778899分享：數(shù)據(jù)結(jié)構(gòu) 【基礎(chǔ)算法總結(jié)】鏈表

http://yzkb.51969.com/

推薦文章