柚子快報激活碼778899分享：數(shù)據(jù)結構 【基礎算法總結】鏈表

http://yzkb.51969.com/

鏈表

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

點贊??收藏??關注?? 你的支持是對我最大的鼓勵，我們一起努力吧!??

1.鏈表常用技巧和操作總結

常用技巧

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

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

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

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

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

4.快慢指針

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

鏈表中的常用操作

1.創(chuàng)建一個新節(jié)點 new

2.尾插

3.頭插

2.兩數(shù)相加

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

題目分析：

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

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

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

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

class Solution {

public:

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

ListNode* newhead, *tail;

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

ListNode* cur1 = l1, *cur2 = l2;

int t = 0; // 記錄進位

while(cur1 || cur2 || t)

{

// 先加上第一個鏈表

if(cur1)

{

t += cur1->val;

cur1 = cur1->next;

}

// 加上第二個鏈表

if(cur2)

{

t += cur2->val;

cur2 = cur2->next;

}

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

tail = tail->next;

t /= 10;

}

//防內存泄漏

// tail = newhead->next;

// delete newhead;

// return tail;

return newhead->next;

}

};

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

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

題目分析：

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

算法原理：

解法一：遞歸

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

引入一個頭節(jié)點，這樣就減少判斷邊界的問題。如果不引入，交換前兩個節(jié)點和后面的節(jié)點寫法是不一樣的，因為還要返回頭指針，所以就只能先處理前兩個找到最終返回的頭節(jié)點，然后在處理后面的。這樣太麻煩了。引入頭節(jié)點，因為已經(jīng)有了頭節(jié)點所有后面處理邏輯都是一樣的。

因為我們要兩兩交換，這里我們需要四個指針。不要吝嗇空間，大膽去定義變量 ，這樣交換指針的時候，不用擔心代碼順序導致找不到鏈表的問題，有了這四個指針隨便先寫那一步。交換之后指針都移動一下。

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

可以看到當cur或者next為空的時候就結束了。

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é)點

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. 重排鏈表

題目分析：

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

算法原理：

解法：模擬

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

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

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

因為這道題比較特殊可以將slow->next 后面逆序，因為你會發(fā)現(xiàn)逆序完之后中間位置還是在一起的。因此可以大膽將slow節(jié)點給第一個鏈表。

第二種逆序策略：從slow位置開始逆序

兩種策略都是可以的。

但是如果使用頭插法逆序，建議還是第一種策略，因為我們是想讓兩個鏈表斷開的。如果想逆序后鏈表還是在一起的，就用第二種策略。

第一種策略

class Solution

{

public:

void reorderList(ListNode* head)

{

// 處理邊界情況

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

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

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; // 注意把兩個鏈表給斷開

while(cur)

{

ListNode* next = cur->next;

cur->next = head2->next;

head2->next = cur;

cur = next;

}

// 3. 合并兩個鏈表 - 雙指針

ListNode* ret = new ListNode(0);

ListNode* prev = ret;

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

while(cur1)

{

// 先放第?個鏈表

prev->next = cur1;

cur1 = cur1->next;

prev = prev->next;

// 再放第?個鏈表

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é)點 -> 快慢指針(畫圖考慮slow的落點在哪里)

ListNode* fast = head, *slow = head;

while(fast && fast->next)

{

slow = slow->next;

fast = fast->next->next;

}

// 2.將slow以及后面鏈表翻轉 -> 頭插法

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

while(cur)

{

next = cur->next;

cur->next = phead;

phead = cur;

cur = next;

}

// 3.合并兩個鏈表 -> 雙指針

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 個升序鏈表

題目鏈接： 23. 合并 K 個升序鏈表

題目分析：

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

算法原理：

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

但是時間復雜度很恐怖，假設每一個鏈表長度為n，共有k個鏈表?？春喜状斡行蜴湵怼Ｈ绻堑谝粋€鏈表，需要合并k-1次，并且長度為n，所以第一個鏈表 時間復雜度 n(k-1)。第二個鏈表n(k-2)。。。所以最終時間復雜度為O(nk^2)

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

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

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

如何快速找到誰是K個節(jié)點中誰是較小的那個呢？ 利用優(yōu)先級隊列。

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

堆每次調整logk，一共進入nk個，所以這個時間復雜度O(nklogk)

class Solution

{

public:

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

//因此指針并不是遞增

//所以自己定義一個仿函數(shù)用來支持將最小節(jié)點放在棧頂

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();

//進

if(cur->next)

pq.push(cur->next);

}

return newhead->next;

}

};

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

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

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

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

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

此時我們就可以用遞歸來實現(xiàn)這個策略。并且和歸并排序過程是一樣的。

歸并排序先分然后才合，時間復雜度我們緊盯每一個鏈表節(jié)點執(zhí)行多少次。分就是一個完全二叉樹。每一個鏈表都會合并，合并次數(shù)是這個數(shù)的高度次，假設有k個鏈表樹高度logk，每一個鏈表都執(zhí)行l(wèi)ogk合并，一共有k個鏈表，每一個鏈表有n個節(jié)點，所以時間復雜度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 個一組翻轉鏈表

題目鏈接：25. K 個一組翻轉鏈表

題目分析：

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

算法原理：

解法：模擬

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

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

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.重復 n 次: 長度為 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.把不需要翻轉的接上

prev->next = cur;

prev = newhead->next;

delete newhead;

return prev;

}

};

柚子快報激活碼778899分享：數(shù)據(jù)結構 【基礎算法總結】鏈表

http://yzkb.51969.com/

推薦文章