在鏈表算法題（上）長中我們已經(jīng)學(xué)習(xí)了一系列的鏈表算法題，那么在本篇中我們將繼續(xù)來學(xué)習(xí)鏈表的算法題，接下來就繼續(xù)來破解鏈表的算法題吧！

---

1.相交鏈表

160. 相交鏈表 - 力扣（LeetCode）

通過以上的題目的描述該算法題要我們實現(xiàn)的代碼功能是判斷兩條鏈表是否相交，如果相較的話就返回相較節(jié)點的指針，不相較就返回NULL

那么在實現(xiàn)該算法題的代碼之前先要來分析如何實現(xiàn)判斷是否是相交鏈表

首先來看相交鏈表有什么特征呢？來看以下的示例

從以上的示例就可以看出當(dāng)兩個鏈表是相交的，那么在這兩條鏈表內(nèi)一定會有兩個節(jié)點的下一個節(jié)點是相同的。而如果鏈表不是相交的，那么就不會有兩個節(jié)點的下一個節(jié)點是相同的

當(dāng)兩個鏈表是相較的時候我們需要返回的就是以上這個節(jié)點，那么該如何來找出這個相交的節(jié)點呢？

在此我們的解決方法是先定義兩個指針變量一開始分別指向兩個鏈表的第一個節(jié)點，之后通過各遍歷一次兩條鏈表，之后就得到這兩條鏈表各自的節(jié)點個數(shù)，之后將得到的兩個節(jié)點數(shù)大的減小的得到兩鏈表長度的差值，將節(jié)點個數(shù)多的鏈表的定義的節(jié)點指針往后走之前得到的差值，最后將兩個鏈表的指針同時往后遍歷，當(dāng)兩個指針相同時就說明這兩個鏈表為相交鏈表，否則就不相交

例如以下示例：

首先A鏈表個數(shù)為5，B節(jié)點個數(shù)為6，兩個鏈表節(jié)點差值就為1

在定義兩個指向兩個；鏈表的第一個節(jié)點的指針pcur1和pcur2，由于B鏈表為節(jié)點個數(shù)多的鏈表因此將B鏈表的指針pcur2先向后走1步

之后讓pcur1和pcur2同時向后遍歷，之后pcur1和pcur2同時指向c1節(jié)點，這就可以說明A和B這兩個鏈表是相交鏈表

接下來我們就來實現(xiàn)該算法題的代碼
在以下得到兩個鏈表的節(jié)點數(shù)差值使用的是庫函數(shù)abs，該函數(shù)能計算出差值的絕對值

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{ListNode* pcur1=headA;ListNode *pcur2=headB;int count1=0;int count2=0;while(pcur1)//得到第一個鏈表的結(jié)點數(shù){count1++;pcur1=pcur1->next;}while(pcur2)//得到第二個鏈表的節(jié)點數(shù){count2++;pcur2=pcur2->next;}int tmp=abs(count1-count2);//得到兩個鏈表節(jié)點數(shù)的差值ListNode* longlist=headA;ListNode* shortlist=headB;if(count1<count2)//確定長短鏈表{longlist=headB;shortlist=headA;}while(tmp--)//先將長鏈表走tmp步{longlist=longlist->next;}while(longlist && shortlist)//同時遍歷兩個鏈表{if(longlist==shortlist){return longlist;}longlist=longlist->next;shortlist=shortlist->next;}return NULL;
}

2.環(huán)形鏈表I

141. 環(huán)形鏈表 - 力扣（LeetCode）

根據(jù)以上的題目描述就可以看出該算法題要我們實現(xiàn)的是判斷鏈表是否為循環(huán)鏈表，在此循環(huán)鏈表是指鏈表的尾節(jié)點不在是連接NULL，而是連接鏈表中的其中一個節(jié)點

那么使用什么方法能判斷鏈表是否為循環(huán)鏈表呢？

在此我們使用的是之前學(xué)習(xí)過的前后指針法，首先定義有兩個指針變量fast和slow，之后fast指針每次走兩步，slow指針每次走一步，到最后如果fast指針和slow相遇就說明該鏈表為循環(huán)鏈表

例如以下示例：

要判斷以上鏈表是否為循環(huán)鏈表我們來看看使用前后指針法的過程是什么樣的，首先定義快指針fast和滿指針slow，之后讓fast和slow遍歷鏈表

?正如上圖所示slow指針和fast指針在節(jié)點-4相遇，這就說明該鏈表為循環(huán)鏈表為循環(huán)鏈表

接下來我們就來實現(xiàn)該算法題的代碼

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) 
{ListNode* fast,*slow;fast=slow=head;while(fast && fast->next){fast=fast->next->next;slow=slow->next;if(fast==slow){return true;}}return false;
}

在解決了以上的算法題后我們就要思考為什么快指針每次走兩步，慢指針走一步可以相遇，有沒有可能遇不上呢？

slow一次走?步，fast一次走2步，fast先進環(huán)，假設(shè)slow也走完入環(huán)前的距離，準備進環(huán)，此時fast和slow之間的距離為N，接下來的追逐過程中，每追擊?次，他們之間的距離縮小1步

這時在追擊過程中fast和slow之間的距離變化：

因此，在帶環(huán)鏈表中慢指針走一步，快指針走兩步最終一定會相遇。

那么在解決以上問題后思考快指針一次走3步，走4步，...n步行嗎?

step1:
按照上面的分析，慢指針每次走一步，快指針每次走三步，此時快慢指針的最大距離為N，接下來的追逐過程中，每追擊一次，他們之間的距離縮小2步
追擊過程中fast和slow之間的距離變化：

分析:
1、如果N是偶數(shù)，第一輪就追上了
2、如果N是奇數(shù)，第一輪追不上，快追上，錯過了，距離變成-1，即C-1，進入新的一輪追擊
? ?a：C-1如果是偶數(shù)，C-1如果是偶數(shù)，那么下一輪就追上了
? ? b：C-1如果是奇數(shù)，那么就永遠都追不上? ? ? ? ? ? ? ? ? ? ? ? ??
總結(jié)一下追不上的前提條件：N是奇數(shù)，C是偶數(shù)

step2：

在以上的step1中我們得出當(dāng)fast追不上的前提條件：N是奇數(shù)，C是偶數(shù)，那么接下來我們就要繼續(xù)分析這種情況是否會出現(xiàn)

假設(shè)：
環(huán)的周長為C，頭結(jié)點到slow結(jié)點的長度為L，slow走一步，fast走三步，當(dāng)slow指針入環(huán)后，slow和fast指針在環(huán)中開始進行追逐，假設(shè)此時fast指針已經(jīng)繞環(huán)x周。
在追逐過程中，快慢指針相遇時所走的路徑長度:

由于慢指針走一步，快指針要走三步，因此得出： 3 * 慢指針路程 = 快指針路程 ，即：

對上述公式繼續(xù)分析：由于偶數(shù)乘以任何數(shù)都為偶數(shù)，因此 2L 一定為偶數(shù)，則可推導(dǎo)出可能得情
況：
? 情況1：偶數(shù) = 偶數(shù) - 偶數(shù)
? 情況2：偶數(shù) = 奇數(shù) - 奇數(shù)

由step1中（1）得出的結(jié)論，如果N是偶數(shù)，則第一圈快慢指針就相遇了。
由step1中（2）得出的結(jié)論，如果N是奇數(shù)，則fast指針和slow指針在第一輪的時候套圈了，開始進行下一輪的追逐；當(dāng)N是奇數(shù)，要滿足以上的公式，則 (x+1)C 必須也要為奇數(shù)，即C為奇數(shù)，滿足（2）a中的結(jié)論，則快慢指針會相遇

因此， step1 中的 N是奇數(shù)，C是偶數(shù)不成立，既然不存在該情況，則快指針一次走3步最終一定也可以相遇。

因此快指針一次走4、5.....步最終也會相遇，其證明方式同上

注：雖然已經(jīng)證明了快指針不論走多少步都可以滿足在帶環(huán)鏈表中相遇，但是在編寫代碼的時候會有額外的步驟引入，涉及到快慢指針的算法題中通常習(xí)慣使用慢指針走?步快指針走兩步的方式。

3.環(huán)形鏈表II

142. 環(huán)形鏈表 II - 力扣（LeetCode）

在以上環(huán)形鏈表I中我們已經(jīng)實現(xiàn)了如何判斷一個鏈表是否為環(huán)形鏈表，接下來我們在環(huán)形鏈表算法題中我們將跟進一步當(dāng)鏈表是環(huán)形鏈表時我們還要返回鏈表進入環(huán)的第一個節(jié)點

那么要如何才能找到環(huán)形鏈表進入環(huán)的第一個節(jié)點呢？接下來我們要來了解一個性質(zhì)

讓一個指針從鏈表起始位置開始遍歷鏈表,同時讓?個指針從判環(huán)時相遇點的位置開始繞環(huán)運
行,兩個指針都是每次均走一步,最終肯定會在入口點的位置相遇。

例如以下示例：

根據(jù)使用快慢指針法我們就可以的到以上鏈表兩指針的相遇節(jié)點為-4

在此之后我們再定義一個指針變量pcur指向鏈表的第一個節(jié)點，之后讓pcur指針和fast指針同時遍歷，當(dāng)這兩個指針指向同一個節(jié)點時，指針指向的節(jié)點就是入環(huán)前的節(jié)點

接下來我們就來實現(xiàn)該算法題的代碼

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head)
{ListNode* fast,*slow;fast=slow=head;while(fast&& fast->next){fast=fast->next->next;slow=slow->next;if(slow==fast){ListNode* pcur=head;while(pcur!=fast){pcur=pcur->next;fast=fast->next;}return fast;}}return NULL;
}

在解決了以上的算法題后我們就要證明為什么在環(huán)形鏈表中以上的這種性質(zhì)：

在以上圖示當(dāng)中H為鏈表的起始點，E為環(huán)入口點，M與判環(huán)時候相遇點?

在此我們設(shè)環(huán)的長度為R，H到E的距離為L，E到M的距離為 X ，則：M到E的距離為 R-X

由于快指針和滿指針走過的路徑分別為

又因為快指針走過的路徑長度為滿指針走過的路徑長度的兩倍，這時就能得到以下的公式

根據(jù)以上公式就可以推斷出以下公式：

在此可以繼續(xù)得到

當(dāng)慢指針進入環(huán)時，快指針可能已經(jīng)在環(huán)中繞了n圈了，n?少為1因為：快指針先進環(huán)走到M的位置,，最后又在M的位置與慢指針相遇

所以以上公式n可能為1,2,3,4......，n的大小取決于環(huán)的大小，環(huán)越小n越大，在此極端情況下，假設(shè)n=1，此時： L=R-X

根據(jù)L=R-X即可說明：?個指針從鏈表起始位置運行，?個指針從相遇點位置繞環(huán)，每次都走?步，兩個指針最終會在入口點的位置相遇

4.隨機鏈表的復(fù)制

138. 隨機鏈表的復(fù)制 - 力扣（LeetCode）

根據(jù)以上的題目描述可以看出該算法題和我們之前解決的題不同，在該算法題中的鏈表節(jié)點中的有三個成員變量，相比正常的鏈表節(jié)點多了一個隨機的指針random。在此題目要我們實現(xiàn)的是鏈表的拷貝，注意在此不是將原鏈表內(nèi)的指針復(fù)制一份，這種只是淺拷貝，在此算法題中我們要實現(xiàn)的是深拷貝，也就是要額外開一份和原鏈表一樣的內(nèi)存空間，在將原鏈表內(nèi)的數(shù)據(jù)拷貝給新的鏈表

接下來我們就來分析如何來實現(xiàn)鏈表的拷貝

例如以下示例：

?在以上鏈表中若要實現(xiàn)鏈表的拷貝，那么該如何實現(xiàn)呢？

在此你可能會想到可以通過遍歷原鏈表，在每遍歷到一個節(jié)點時就創(chuàng)建一個新的節(jié)點，再將原鏈表節(jié)點內(nèi)的數(shù)據(jù)拷貝給新節(jié)點，之后再將新節(jié)點尾插新鏈表

但是在以上的示例按照這種方法來實現(xiàn)就會發(fā)現(xiàn)問題了，在以上示例的鏈表按照以上的方法來拷貝在第一個節(jié)點時沒問題，當(dāng)?shù)搅说诙€節(jié)點就出現(xiàn)一個問題就是原鏈表第二個節(jié)點中的random指針指向的第一個節(jié)點，但在使用以上方法時第二個節(jié)點中的random無法找到第一個節(jié)點，這時因為單向鏈表中無法向前遍歷鏈表

因此要解決鏈表的拷貝以上的方法行不通，在此我們需要想其他的方法
接下來就來講解一種很妙的方法

首先是在原鏈表基礎(chǔ)上復(fù)制鏈表

在此我們先定義兩個指針變量pcur和Next分別指向原鏈表第一個節(jié)點和第二個節(jié)點

之后創(chuàng)建一個新的節(jié)點并且將第一個節(jié)點內(nèi)的值val拷貝到新節(jié)點中，再將新節(jié)點插入到pcur和Next節(jié)點中間，完成以上操作后讓pcur指向Next指向的節(jié)點，Next指向其next指針指向的節(jié)點

之后在遍歷原鏈表每個節(jié)點時重復(fù)以上的操作，直到pcur指向NULL停止操作，這時原鏈表就變?yōu)橐韵滦问?/span>

在以上我們創(chuàng)建的新節(jié)點只進行了val的拷貝，那么接下來就來對random來進行拷貝，要進行random的拷貝接下來要再創(chuàng)建一個指針變量copy讓其一開始指向創(chuàng)建的第一個新節(jié)點，并且之后還要讓pcur和Next指針重新回到初始位置

之后繼續(xù)置random指針?

在此pcur指向節(jié)點的random為NULL，就讓這時copy指向的節(jié)點內(nèi)的random也置為NULL，之后讓pcur指向Next指向的節(jié)點，Next指向其next指針的next指向的節(jié)點，copy指向改變后的pcur的next指針指向的節(jié)點

之后再遍歷原鏈表，當(dāng)pcur指向節(jié)點內(nèi)的random不為NULL時，讓copy內(nèi)的random指針指向pcur內(nèi)random指向的節(jié)點next指針指向的節(jié)點，也就是copy->random=pcur->random->next，最后當(dāng)pcur為NULL停止，這時原鏈表就變?yōu)橐韵滦问?/span>

完成以上操作后最后就要將原鏈表和賦值鏈表斷開

在此讓pcur的next指針指向copy的next指針指向的節(jié)點，copy的next指針指向pcur的next指針指向的節(jié)點next指針指向的節(jié)點，之后讓copy和pcur都往后走一步

之后再遍歷原鏈表，重復(fù)以上的操作，這時原鏈表就變?yōu)橐韵滦问?/span>

?

通過以上示例的講解就可以發(fā)現(xiàn)鏈表的復(fù)制分為以下3步：

接下來就來實現(xiàn)該算法題的代碼

/*** Definition for a Node.* struct Node {*     int val;*     struct Node *next;*     struct Node *random;* };*/typedef struct Node Node;Node* NewNode(int x){Node* newnode=(Node*)malloc(sizeof(Node));newnode->val=x;newnode->next=newnode->random=NULL;return newnode;}struct Node* copyRandomList(struct Node* head)
{if(head==NULL){return head;}Node* pcur=head;
//在原鏈表基礎(chǔ)上復(fù)制鏈表while(pcur){Node* Next=pcur->next;Node*newnode=NewNode(pcur->val);newnode->next=Next;pcur->next=newnode;pcur=pcur->next->next;}
//置random指針pcur=head;while(pcur!=NULL){Node* newpcur=pcur->next;if(pcur->random!=NULL){newpcur->random=pcur->random->next;}pcur=newpcur->next;}
//將原鏈表和賦值鏈表斷開pcur=head;Node* newhead,*newptail;newhead=newptail=pcur->next;while(pcur->next->next){pcur=pcur->next->next;newptail->next=pcur->next;newptail=newptail->next;}return newhead;
}

以上就是鏈表算法題的全部內(nèi)容了，希望能得到你的點贊、收藏