數(shù)據(jù)結(jié)構：帶環(huán)單鏈表基礎OJ練習筆記(leetcode142. 環(huán)形鏈表 II)(leetcode三題大串燒)

這篇具有很好參考價值的文章主要介紹了數(shù)據(jù)結(jié)構：帶環(huán)單鏈表基礎OJ練習筆記(leetcode142. 環(huán)形鏈表 II)(leetcode三題大串燒)。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

一.前言?

二.leetcode160.?相交鏈表?

1.問題描述

2.問題分析與求解

三.leetcode141.?環(huán)形鏈表

1.問題描述

2.代碼思路?

3.證明分析?

下一題會用到的重要小結(jié)論：

四.leetcode142.?環(huán)形鏈表 II

1.問題描述

2.問題分析與求解

Judgecycle接口：

方法一：

方法二：?

一.前言?

單鏈表和帶環(huán)單鏈表OJ題是筆試面試?？嫉念}目,本期是關于帶環(huán)單鏈表基礎題的刷題小筆記(前兩個題的求解過程可以用于求解第三個題哦!)

二.leetcode160.?相交鏈表?

leetcode鏈接：160. 相交鏈表 - 力扣（Leetcode）

1.問題描述

給你兩個單鏈表的頭節(jié)點的地址?headA?和?headB?，請你找出并返回兩個單鏈表相交部分的起始節(jié)點。如果兩個鏈表不存在相交節(jié)點，返回?null?。

比如圖示兩個鏈表：

已知a1和b1的地址,編寫程序返回c1的地址。

測試用例中的鏈表不存在環(huán)

函數(shù)返回結(jié)果后，兩個鏈表必須保持其原始結(jié)構?

題解接口：

class Solution 
{
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        
    }
};

2.問題分析與求解

數(shù)據(jù)結(jié)構：帶環(huán)單鏈表基礎OJ練習筆記(leetcode142. 環(huán)形鏈表 II)(leetcode三題大串燒)

方法一:

先各自求出兩個鏈表的長度,并求出它們長度的差值：

數(shù)據(jù)結(jié)構：帶環(huán)單鏈表基礎OJ練習筆記(leetcode142. 環(huán)形鏈表 II)(leetcode三題大串燒)

然后再用兩個指針來分別遍歷兩個鏈表,其中遍歷較長鏈表的指針要先向前走N步(N表示兩個鏈表長度的差值),然后兩個指針再一起向前遍歷兩個鏈表,若鏈表存在交點,則兩個指針必定會在交點相遇：

數(shù)據(jù)結(jié)構：帶環(huán)單鏈表基礎OJ練習筆記(leetcode142. 環(huán)形鏈表 II)(leetcode三題大串燒)

題解代碼：

class Solution 
{
public:
    int countNode(ListNode * head)   //封裝一個求節(jié)點個數(shù)的函數(shù)
    {
        int count = 0;
        while(head)
        {
            count++;
            head=head->next;
        }
        return count;
    }
    ListNode * foundNode(ListNode* longlist,ListNode* shortlist,int diff)
    //封裝一個求第一個相交節(jié)點的函數(shù)
    {
        while(diff)                   //遍歷長鏈表的指針先向前走diff步
        {
            longlist = longlist->next;
            --diff;
        }
        while(longlist && shortlist)  //兩指針一起向前走直到相遇或指向空指針
        {
            if(longlist == shortlist)
            {
                return longlist;
            }
            longlist=longlist->next;
            shortlist=shortlist->next;
        }
        return nullptr;               //最終指向空指針則說明兩表不相交
    }
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        int countA = countNode(headA);
        int countB = countNode(headB);
        if(countA>=countB)
        {
            return foundNode(headA,headB,countA-countB);
        }
        else
        {
            return foundNode(headB,headA,countB-countA);
        }
    }
};

這個方法思路比較簡單但是不夠簡潔優(yōu)雅,還有一個更簡潔優(yōu)雅的解法。

方法二：

我們先考慮遍歷表A的指針：當遍歷表A的指針走到尾節(jié)點后,我們令其返回指向表B的頭節(jié)點,此后如果該指針繼續(xù)向前走countB步,則指針會來到兩個鏈表的第一個相交節(jié)點，此時遍歷表A的指針總共向前走了(countA + public + countB)次,如圖：

類似地,遍歷B表的指針走到表尾后,我們令其返回指向表A的頭節(jié)點,此后如果該指針再向前走countA步則同樣會來到兩表的第一個相交節(jié)點.此時遍歷B表的指針同樣總共向前走了(countA+countB+public)次.

因此如果我們讓遍歷表A和表B的指針同時向前遍歷鏈表,當他們走到表尾后,則令他們返回指向另外一個鏈表的頭節(jié)點,兩指針最終必定會在兩鏈表第一個相交節(jié)點相遇(此時兩個指針同時向前走了(countA + countB + public)次)。如圖:

題解代碼：
class Solution 
{
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        ListNode * ptrA = headA;
        ListNode * ptrB = headB;
        while(ptrA!=ptrB)
        {
            ptrA = (ptrA==nullptr)? headB : ptrA->next; //(ptrA==nullptr)代表指針指向A表尾
            ptrB = (ptrB==nullptr)? headA : ptrB->next; //(ptrB==nullptr)代表指針指向B表尾
        }
        return ptrA;
    }
};
?若兩個鏈表不相交,最終兩個指針會同時變?yōu)榭罩羔?函數(shù)會返回空指針

三.leetcode141.?環(huán)形鏈表

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

1.問題描述

給你一個鏈表的頭節(jié)點的地址head?，判斷鏈表中是否有環(huán)。

(如果鏈表中有某個節(jié)點,可以通過連續(xù)跟蹤?next?指針再次到達,則鏈表中存在環(huán).)

如果鏈表中存在環(huán)?，則返回?true?。否則，返回?false?。

比如：

題解接口：

class Solution 
{
public:
    bool hasCycle(ListNode *head) 
    {
        
    }
};

2.代碼思路?

本題的代碼思路很簡單,利用的是快慢指針法,兩個指針同時遍歷鏈表,快指針一次走兩步,慢指針一次走一步。

如果鏈表中不存在環(huán),則快指針會率先達到表尾。

如果鏈表中存在環(huán),則快慢指針最終會在環(huán)中相遇。

題解代碼：
class Solution 
{
public:
    bool hasCycle(ListNode *head) 
    {
        if(nullptr == head || nullptr == head->next)//單節(jié)點和無節(jié)點鏈表做額外判斷
        {
            return false;
        }
        ListNode* fast = head->next->next; //讓快指針先走兩步,慢指針走一步讓它們指向不同節(jié)點
        ListNode* slow = head->next;
        while((fast && fast->next && fast!=slow))
        {
            fast=fast->next->next;         //快指針一次走兩步
            slow=slow->next;               //慢指針一次走一步
        }
        return (fast==slow)? true : false; //判斷兩指針是否相遇并確定返回值(若無環(huán)fast一定不等 
                                           //slow)
    }
};
然而本題的關鍵并不在于代碼如何寫,而是在于如何去證明上述求解思路的合理性。

接下來我們嘗試對快慢指針法在本題中的合理性做一個比較嚴格的證明。

3.證明分析?

下文的所謂的距離指的是兩個鏈表節(jié)點位置之間指針鏈的數(shù)目。

我們先將帶環(huán)鏈表用一個概念圖表示一下：?

?我們令快慢指針同時從鏈表頭節(jié)點出發(fā)：(fast=fast->next->next表示快指針一次走兩步)(slow=slow->next表示慢指針一次走一步)

如果鏈表中不存在環(huán),易知快指針fast必然率先結(jié)束遍歷鏈表的過程(fast或fast->next指向空),此時返回false。

如果鏈表中存在環(huán),那么快指針會率先進環(huán),之后慢指針入環(huán)時,快指針此時一定處于環(huán)中某個位置:

此后快指針開始在環(huán)中追趕慢指針,假設慢指針入環(huán)時,快指針與慢指針的距離為N(N小于或等于環(huán)的總長度減一)(N為某一個正整數(shù))

慢指針入環(huán)時兩指針的環(huán)上距離是整數(shù)N.快指針每次循環(huán)前進兩步,慢指針每次循環(huán)前進一步,可知兩個指針的距離每次循環(huán)后會縮小1,則快指針必定會在環(huán)上某個點與慢指針相遇(即fast==slow，此時說明鏈表中存在環(huán))

下一題會用到的重要小結(jié)論：

另外還有一個重要小結(jié)論：快慢指針相遇時,慢指針在環(huán)上走過的距離一定小于環(huán)的長度(因為N小于或等于環(huán)的總長度減一)?(該結(jié)論在下一題中會用到)

更進一步的思考：如果快指針一次走三步或者n步(n>2),慢指針仍然一次走一步,那么是否還能確保快慢指針一定會在環(huán)中相遇？

答案是否定的,我們可以規(guī)定讓快指針一次走三步來做一下分析,設當慢指針剛?cè)氕h(huán)時,兩個指針的距離為N：

快指針一次走三步,那么每次循環(huán)兩個指針的距離會縮小2

假如N是偶數(shù),那么快指針最終會與慢指針相遇

假如N是奇數(shù),那么快指針追上慢指針后會處于慢指針的前一個位置。(整除余1)

此時快指針重新開始追趕慢指針:設環(huán)的長度為X,則此時相當于快指針與慢指針的距離為X-1

若X-1為偶數(shù),那么快指針最終可以與慢指針相遇

若X-1為奇數(shù),那么快指針追上慢指針后會又一次處于慢指針的前一個位置。緊接著就開始了無限循環(huán)追趕,兩個指針永遠都不會相遇

同樣地,若令快指針一次走3,4,5...n步,通過數(shù)學歸納思維,我們同樣能分析出(在各種不同的環(huán)長度的鏈表中)可能會出現(xiàn)和上述類似的無限追趕的情況,因此可以得出結(jié)論:快指針每次必須比慢指針多走1步才能確保(在任何帶環(huán)鏈表中)兩指針最終會在環(huán)中會相遇。

四.leetcode142.?環(huán)形鏈表 II

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

1.問題描述

該題在上一題的基礎上,要求我們編寫的接口能夠返回鏈表開始入環(huán)的第一個節(jié)點的地址。如果鏈表無環(huán)，則返回?nullptr.

比如：

題解接口：

class Solution
{
public:
    ListNode* detectCycle(ListNode* head)
    {
        
    }
};

2.問題分析與求解

第一步：

本題的求解建立在上一個題目的基礎之上.

我們先編寫一個額外的Judgecycle接口,用于判斷鏈表是否帶環(huán),并且返回快慢指針在環(huán)中相遇位置節(jié)點的地址(鏈表不帶環(huán)則返回空指針)。

數(shù)據(jù)結(jié)構：帶環(huán)單鏈表基礎OJ練習筆記(leetcode142. 環(huán)形鏈表 II)(leetcode三題大串燒)

Judgecycle接口：

    ListNode* Judgecycle(ListNode* head)
    {
        if(nullptr==head || nullptr == head->next)
        {
            return nullptr;
        }
        ListNode *fast =head->next->next;
        ListNode *slow = head->next;
        while(fast && fast->next && fast!=slow)
        {
            fast=fast->next->next;
            slow = slow ->next;
        }
        return (fast&&fast->next)? fast : nullptr;//(fast或fast->next為空則表示鏈表無環(huán))
    }                                             //(為空說明fast走到表尾)

若鏈表帶環(huán),返回的fast指針就是快慢指針在環(huán)中相遇的位置的節(jié)點的地址
該接口的原理參見上一題的分析。

在題解接口中我們用一個temmet指針來接收Judgecycle接口的返回值

 

class Solution
{
public:
    ListNode* Judgecycle(ListNode* head)
    {
        if(nullptr==head || nullptr == head->next)
        {
            return nullptr;
        }
        ListNode *fast =head->next->next;
        ListNode *slow = head->next;
        while(fast && fast->next && fast!=slow)
        {
            fast=fast->next->next;
            slow = slow ->next;
        }
        return (fast&&fast->next)? fast : nullptr;//(fast或fast->next為空則表示鏈表無環(huán))
    }                                             //(為空說明fast走到表尾)


                                             
    ListNode* detectCycle(ListNode* head)         //題解接口
    {
       ListNode * temmet = Judgecycle(head);
       ListNode* temhead = head;
       //其他操作步驟
    }
};

基于上面的Judgecycle接口,接下來我們有兩種方法可以求解本題

方法一：

假設環(huán)中temmet指針(指向Judgecycle接口中快慢指針在環(huán)中相遇位置節(jié)點)與環(huán)入口節(jié)點的距離為N

假設鏈表頭節(jié)點與環(huán)入口節(jié)點的距離為M

假設環(huán)的總長度(距離)為C(不包括M)

接著我們來分析N,M,C之間存在著什么樣的數(shù)學關系.

利用前一個題的一個重要結(jié)論(見目錄)：Judgecycle接口中快慢指針相遇時,慢指針在環(huán)上走過的距離一定小于環(huán)的長度
于是：在Judgecycle接口中,快慢指針相遇時慢指針在鏈表中走過的總距離為(M+C-N)

進一步可以得出,快慢指針相遇時快指針在鏈表中走過的總距離為2*(M+C-N)

假設快慢指針相遇時,快指針已經(jīng)在環(huán)中走了n圈，那么我們便可以用另外一種方式表示出快慢指針相遇時快指針在鏈表中走過的總距離：M+n*C+(C-N)

于是得到方程：2*(M+C-N)=M+n*C+(C-N)

化簡可得：M+C-N = n*C 即：M=(n-1)*C + N? (M,C,N,n都為整數(shù))

令一個指針temhead初始位置指向鏈表頭節(jié)點,另外一個指針temmet初始位置指向環(huán)中快慢指針相遇的位置(由Judgecycle接口返回)
兩個指針同時開始遍歷鏈表,根據(jù)關系式M=(n-1)*C + N?(M,C,N,n都為整數(shù))可知兩個指針必然在鏈表的入環(huán)節(jié)點相遇。返回指針的值即可得到答案。
    ListNode* detectCycle(ListNode* head)
    {
        ListNode* temmet = Judgecycle(head);      //快慢指針相遇位置節(jié)點的地址
        ListNode* temhead = head;
        if (temmet) //判斷temmet是否為空,為空說明鏈表不帶環(huán)
        {
            while (temhead != temmet)             //兩個指針同時向前遍歷鏈表直到相遇
            {
                temmet = temmet->next;
                temhead = temhead->next;
            }
            return temmet;                        //返回相遇位置節(jié)點地址
        }
        return nullptr;      //代表鏈表無環(huán)
    }
題解代碼：
class Solution
{
public:
    ListNode* Judgecycle(ListNode* head)
    {
        if(nullptr==head || nullptr == head->next)
        {
            return nullptr;
        }
        ListNode *fast =head->next->next;
        ListNode *slow = head->next;
        while(fast && fast->next && fast!=slow)
        {
            fast=fast->next->next;
            slow = slow ->next;
        }
        return (fast&&fast->next)? fast : nullptr;//(fast或fast->next為空則表示鏈表無環(huán))
    }                                             //(為空說明fast走到表尾)   

    ListNode* detectCycle(ListNode* head)
    {
        ListNode* temmet = Judgecycle(head);      //快慢指針相遇位置節(jié)點的地址
        ListNode* temhead = head;
        if (temmet) //判斷temmet是否為空,為空說明鏈表不帶環(huán)
        {
            while (temhead != temmet)             //兩個指針同時向前遍歷鏈表直到相遇
            {
                temmet = temmet->next;
                temhead = temhead->next;
            }
            return temmet;                        //返回相遇位置節(jié)點地址
        }
        return nullptr;      //代表鏈表無環(huán)
    }
};

方法二：?

數(shù)據(jù)結(jié)構：帶環(huán)單鏈表基礎OJ練習筆記(leetcode142. 環(huán)形鏈表 II)(leetcode三題大串燒)

確定了Judgecycle接口中快慢指針在環(huán)中相遇的位置后,我們在兩指針相遇的節(jié)點處將環(huán)斷開
于是問題就轉(zhuǎn)換成了求兩個相交鏈表第一個相交節(jié)點地址的問題(問題求解參見本期第一個OJ題)?,其中快慢指針在環(huán)中相遇位置的節(jié)點作為斷環(huán)后新鏈表的頭節(jié)點

因此我們可以調(diào)用前兩個題的接口來求解本題：

class Solution
{
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)                        
    //求相交鏈表第一個交點的接口
    {
        ListNode * ptrA = headA;
        ListNode * ptrB = headB;
        while(ptrA!=ptrB)
        {
            ptrA = (ptrA==nullptr)? headB : ptrA->next; //(ptrA==nullptr)代表指針指向A表尾
            ptrB = (ptrB==nullptr)? headA : ptrB->next; //(ptrB==nullptr)代表指針指向B表尾
        }
        return ptrA;
    }
public:
    ListNode* Judgecycle(ListNode* head)          //求快慢指針在環(huán)中相遇位置的接口
    {
        if(nullptr==head || nullptr == head->next)
        {
            return nullptr;
        }
        ListNode *fast =head->next->next;
        ListNode *slow = head->next;
        while(fast && fast->next && fast!=slow)
        {
            fast=fast->next->next;
            slow = slow ->next;
        }
        return (fast&&fast->next)? fast : nullptr;//(fast或fast->next為空則表示鏈表無環(huán))
    }                                             //(為空說明fast走到表尾)   

    ListNode* detectCycle(ListNode* head)
    {
        ListNode* temmet = Judgecycle(head);
        if (temmet)                                 //判斷temmet是否為空,為空說明鏈表不帶環(huán)
        {
            ListNode* breakpoint = temmet;
            while(breakpoint->next != temmet)       //找到環(huán)中的斷開點
            {
                breakpoint = breakpoint->next; 
            }
            breakpoint->next = nullptr;             //將環(huán)斷開
            return getIntersectionNode(temmet,head);//轉(zhuǎn)化為求兩鏈表第一個交點的問題
        }
        return nullptr;                             //代表鏈表無環(huán)
    }
};

數(shù)據(jù)結(jié)構：帶環(huán)單鏈表基礎OJ練習筆記(leetcode142. 環(huán)形鏈表 II)(leetcode三題大串燒)

根據(jù)我們上面各步驟的分析不難得出兩種求解方法的時間復雜度都是O(N),但是方法一會比方法二略高效一些。

數(shù)據(jù)結(jié)構：帶環(huán)單鏈表基礎OJ練習筆記(leetcode142. 環(huán)形鏈表 II)(leetcode三題大串燒) 文章來源地址http://www.zghlxwxcb.cn/news/detail-403433.html

到了這里，關于數(shù)據(jù)結(jié)構：帶環(huán)單鏈表基礎OJ練習筆記(leetcode142. 環(huán)形鏈表 II)(leetcode三題大串燒)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！