1.前言
讓我們緊接上文 單鏈表面試題分享二 ,這篇文章只給大家分享三道題.它們分別是:1.環(huán)形鏈表初階 力扣141題-----2.環(huán)形鏈表進階 力扣142題----- 3.復(fù)制帶隨機指針的鏈表 力扣138題 .值得注意的是這三道題的技巧性很強,是屬于能想到方法實現(xiàn)起來很簡單,想不到方法實現(xiàn)起來很復(fù)雜甚至不能實現(xiàn)的題.這里我提供給大家的思想和方法可能是我們之前出來沒有遇見過也不好想到的方法,證明了這個地方我們已經(jīng)開始上難度了,開始真正的在"玩"鏈表了.
2. 環(huán)形鏈表初階
2.1 審題
先看題:
這個題我們不要去看它的pos之類的,容易誤導(dǎo)我們的思維,這里的pos是是教我們自測輸入的.這個題的意思就是,讓我們判斷一個鏈表是否存在環(huán),如果如果就返回true,不存在返回false.當(dāng)我們拿到這個題的時候會發(fā)現(xiàn)和別的鏈表題不同的是,如果鏈表存在環(huán)的話它是無法用NULL來作為我們循環(huán)結(jié)束的標(biāo)志的,所以這個地方我們得另辟蹊徑. 先給大家說結(jié)論,這個地方我們采用的方法叫做快慢指針法,顧名思義就是一個指針走得快一個指針走得慢, 我們通過畫圖來理解這個方法的第一步:
這個時候,fast剛好進入到我們的環(huán)中,如何進行我們的第二步, 那就是當(dāng)slow指針也進入環(huán)時,這時fast指針在環(huán)中的某一個位置(不管slow指針進環(huán)前fast走了一圈還是多圈),這時我們設(shè)置slow和fast的距離(也就是它們兩個之間的節(jié)點數(shù))為N ,然后我們再來畫圖理解:
因為它們兩個指針每走一次距離減少1,所以它們永遠不會錯過,只要有環(huán)存在,它們就會相遇.下面我們來實現(xiàn)一下代碼:
2.2 代碼實現(xiàn)以及緊急情況的處理方法
bool hasCycle(struct ListNode *head)
{
struct ListNode* slow = head, *fast = head;
while(fast&&fast->next)//fast和fast->next都不為空
{
slow=slow->next;
fast=fast->next->next;
if(slow==fast)
{
return true;
}
}
return false;//如果fast或者fast->next為空證明鏈表中沒有環(huán)
}
代碼實現(xiàn)是很簡單的,但是我們的思路是比較難想到的, 如果我們在參加面試或者比賽的時候遇見了這種題沒有思路,時間也快不夠了的時候,我們可以試著用題目給的條件來讓代碼通過(平時訓(xùn)練不建議這樣做)
bool hasCycle(struct ListNode *head)
{
struct ListNode* cur=head;
int count=0;
while(cur)//遍歷鏈表
{
cur=cur->next;
count++;//題目說節(jié)點數(shù)小于10000
if(count>10000)//所以當(dāng)遍歷到10000遍時一定為環(huán),就返回true
{
return true;
}
}
return false;
}
2.3 延伸問題
其實我們會發(fā)現(xiàn),這個題考驗的其實是我們的算法能力和思維能力,并不是在考我們的代碼水平,所以這個地方的追加問題經(jīng)常出現(xiàn)在面試時面試官的提問中,他第一步會問你這個題目的思路是怎么樣的,他并不會讓你去寫代碼,而是在你回答了你的思路后繼續(xù)追加問你問題:比如:1.為什么為什么slow和fast一定會在環(huán)中相遇?它們會不會在環(huán)中錯過,永遠遇不上?請證明一下-----2.為什么slow走一步fast走兩步,fast能不能走3步?4步?甚至n步?走n步還能不能遇上?請證明一下 這里我們就來探討一下:
2.3.1 為什么slow和fast一定會遇上?
根據(jù)我們前面的推斷其實我們已經(jīng)有了一定認識,那就是當(dāng)slow走一步,fast走兩步的時候它們一定會遇上!
因為我們知道,fast一定是比slow先進入到環(huán)中的,所以當(dāng)slow進入環(huán)之后,我們的fast肯定已經(jīng)在環(huán)中走了某段距離并且停留在某個點上了.這時slow和fast的距離為N,每走一次,N的值就會減一,所以說我們的N不會出現(xiàn)跳過0的這種情況,N一定會在某次slow和fast走后變?yōu)?,這時就代表slow和fast相遇了.
2.3.2 走n步會是什么樣的情況?
這里我們由易到難,先討論slow走一步,fast走三步的情況:還是和之前一樣,當(dāng)slow進環(huán)后,我們令fast和slow的距離為N,目前這種情況它們倆走一次,N的值會減少二,那么我們說什么情況下N能夠順利的減到0呢?很明顯那就是當(dāng)N為2的倍數(shù)的時候(也就是N為偶數(shù)的時候)
我們會發(fā)現(xiàn)當(dāng)N為偶數(shù)的時候我們能夠順利的將N減到0,也就是讓slow和fast相遇,但是當(dāng)N為奇數(shù)時,減到1的時候再減去2會得到-1,也就是fast直接越過了slow.那么當(dāng)它們走了一圈沒有相遇的時候它們后面還會相遇嗎?我們畫圖來探討一下:
可以看見如果第一圈沒有追到不代表永遠追不到,當(dāng)N為奇數(shù)時,追完一圈fast在slow后面一個,所以它們的距離N’就變成了環(huán)的長度減一,這里把它們的距離又看作N’,即N’為偶數(shù)可以追上,N’為奇數(shù)就永遠追不上了,因為當(dāng)N’為奇數(shù)時相當(dāng)于又重復(fù)了我們的第一遍操作. 當(dāng)我們了解了走三步的情況,接下來我們來探討slow走一步,fast走四步的情況:也就是slow和fast每走一次,它們的距離N就減少3,這里有了我們前面的經(jīng)驗很容易想到,如果N為3的倍數(shù),那么N就可以減到0,也就是slow和fast可以相遇.當(dāng)N不為3的倍數(shù)這個地方我們又要來判斷一下:
當(dāng)N不是3的倍數(shù)時有兩種情況,就是最后一次走后,N為-1或者-2;也就是slow和fast的距離變成了環(huán)的長度減一或者環(huán)的長度減二.后面走N步就依此類推了.綜上所述:這個題用slow走一步,fast走兩步是最好的
3. 環(huán)形鏈表進階
3.1 審題
先看題:
這個題相較于我們上一個題多了一個步驟,就是要返回鏈表開始入環(huán)的第一個節(jié)點.這個地方我們還是先用快慢指針來判斷是否有環(huán),slow走一步,fast走兩步,當(dāng)我們判斷了鏈表有環(huán)之后,下一步應(yīng)該怎么做?我們之前說這個地方的題技巧性很強,方法一般很難想到,所以這個地方我先給出結(jié)論,后面再證明 結(jié)論:一個指針從slow和fast的相遇點開始走,寧外一個指針從鏈表頭開始走,他們會在環(huán)的入口點相遇(每個指針一次走一步),下面我們先來證明一下:
當(dāng)我們寫到這個地方就很明了了,我們有:L=(n-1)*C+C-X.這個地方的C-X就相當(dāng)于我們從meetnode點開始走,然后(n-1)*C就相當(dāng)于在環(huán)中走了幾圈,這個地方相當(dāng)于我們一個指針從head開始走(從鏈表的頭),一個指針從meetnode開始走,它們最終會在入環(huán)點相遇(也就是從頭開始走的指針走到距離L時在入環(huán)點,從meetnode開始走的指針也一定在入環(huán)點),期間從meetnode開始走的指針可能會在環(huán)內(nèi)不止走一圈,但是不管它走幾圈它們最終都會相遇. 我們有了思路后,代碼寫起來就很簡單了.
3.2 代碼實現(xiàn)
struct ListNode *detectCycle(struct ListNode *head)
{
struct ListNode* slow=head;
struct ListNode* fast=head;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
if(fast==slow)
{
struct ListNode* meet=fast;
while(meet!=head)
{
meet=meet->next;
head=head->next;
}
return head;
}
}
return NULL;
}
3.3 方法二:相交鏈表法
這個題還有第二種解法,我們之前做過一道相交鏈表的題,這個題可以沿用它的思路來解題,我們還是先找到slow和fast相遇的點記為meetnode,然后我們找到meetnode的下一個節(jié)點設(shè)為phead,將這兩個節(jié)點斷開,將pheaad設(shè)為新鏈表的新頭,將meetnode置為空指針,我們來畫圖看看
這個題我們把一個鏈表拆成兩個鏈表,就從一個環(huán)的問題轉(zhuǎn)換為了兩個鏈表相加的問題,即這個地方list1和list2的第一個相交點就是我們的第一個入環(huán)點.我們之前做過相交鏈表的思路,所以這個題也省去了一點功夫,但是值得注意的是,這個題的題目明確告訴了我們不允許改變鏈表,所以我們這個地方是不能把meetnode->next給置空的,雖然不能改變鏈表,但是這個題還是可以用這個方法來做. 這個地方想嘗試一下這個方法的可以去看我的前一章鏈表題分享二,里面有詳細的相交鏈表的解法.
4. 復(fù)制帶隨機指針的鏈表
4.1審題
先看題:
這個題讓我們把它給的鏈表拷貝一份,然后再返回拷貝的鏈表,并且復(fù)制鏈表中的指針都不應(yīng)指向原鏈表中的節(jié)點 ,假如這個地方?jīng)]有隨機指針random,我們就很好辦,直接一個節(jié)點一個節(jié)點的復(fù)制最后再鏈接起來,這個題難就難在它里面有一個隨機指針,你不知道原來的節(jié)點的隨機指針指向的是哪一個位置,所以如果我們按照平常的思維解題,也就是暴力求解的話時間復(fù)雜度為O(N^2),實現(xiàn)起來也比較復(fù)雜,所以這個地方我們不要這種"笨辦法".我們將拷貝的鏈表和原先的鏈表建立某種聯(lián)系,這里我直接說結(jié)論:第一步:將要拷貝的鏈表一個一個拷貝后插入原先的鏈表當(dāng)中,拷貝的鏈表的每一個節(jié)點在原先的鏈表對應(yīng)的節(jié)點后面,使兩個鏈表合并為一個如圖:
當(dāng)我們按照上面的方式將它們鏈接起來后,我們可以觀察到原先的節(jié)點2的隨機指針指向的是原先的節(jié)點1;那我們希望拷貝鏈表的節(jié)點2也指向拷貝鏈表的結(jié)點1,這個時候它們就有一個關(guān)系式, 我們拷貝鏈表節(jié)點X的隨機指針等于原先鏈表的節(jié)點X指向的隨機指針的next,放在這個題也就是拷貝鏈表的13的隨機指針指向的位置是原先鏈表的13指向的隨機指針的next;這里我們的第二步就出來了:在我們鏈接好的鏈表基礎(chǔ)上,用我們剛剛發(fā)現(xiàn)的規(guī)律將拷貝鏈表所有的節(jié)點的隨機指針的指向都給確定下來.
當(dāng)我們解決了隨機指針的問題后,這個題就很好辦了,現(xiàn)在我們進行我們的最后一步,第三步:將我們的拷貝節(jié)點全部截取下來,并且重新鏈接組成一個鏈表(這里用尾插);注意這個地方我們還要還原原先的鏈表(不能說拷貝了一份鏈表就把原先的鏈表給破環(huán)了):
當(dāng)我們推導(dǎo)到這個地方的時候就可以著手寫代碼了.
4.2 代碼的分布實現(xiàn)
4.2.1 第一步:
struct Node* cur=head;
while(cur)//第一步:拷貝節(jié)點插入原節(jié)點中
{
struct Node* copy=(struct Node*)malloc(sizeof(struct Node));
copy->val=cur->val;//copy鏈表的值和原鏈表相同
copy->next=cur->next;//此時cur的next還指向原先鏈表的cur的下一個節(jié)點
cur->next=copy;//這個地方順序不能換,要是先寫這一句那我們就找不到原先鏈表的下一個節(jié)點了
cur=copy->next;//最后再將cur移動到原先鏈表的下一個位置.
}
我們不斷開辟空間(也就是不斷創(chuàng)建節(jié)點)和原先鏈表的結(jié)點相連接,并且保持val值相同.
4.2.2 第二步
cur=head;//上一步的cur已經(jīng)走到NULL了,這里重新把它置為head
while(cur)//第二步:將拷貝的節(jié)點的random值確定了
{
struct Node* copy=cur->next;//上一個創(chuàng)建的變量copy已經(jīng)在上一個while循環(huán)中銷毀了(開辟的空間和指向沒有銷毀),這里重新定義一個copy變量
if(cur->random==NULL)//當(dāng)原先鏈表的隨機指針指向空,我們就不用花里胡哨了直接將我們的拷貝節(jié)點置空
{
copy->random=NULL;
}
else
{
copy->random=cur->random->next;//這就是我們發(fā)現(xiàn)的規(guī)律
}
cur=copy->next;//cur還是不斷的迭代往后走
}
做完這最具技巧性的一步最后就剩把拷貝節(jié)點截取下來了.
4.2.3 第三步
struct Node* copyhead=NULL,*copyend=NULL;//先定義兩個拷貝鏈表的變量,一個用來返回拷貝鏈表的頭,一個用來迭代往后走
cur=head;//重新將cur置空
while(cur)//我們重新鏈接用的是尾插的方法
{
if(copyhead==NULL)//第一次進循環(huán)時先將copyhead和copyend賦值
{
copyend=copyhead=cur->next;
}
if(copyend->next==NULL)//這個地方是特殊情況,如若不討論特殊情況會報錯解引用空指針
{
cur=NULL;
}
else
{
struct Node* next=copyend->next;//新定義的節(jié)點為原先鏈表的cur的下一個節(jié)點,定義這個變量的目的是當(dāng)我們拆下一個
//拷貝節(jié)點后,我們會找不到下一個原節(jié)點,cur就不能往后迭代著走
copyend->next=next->next;
cur->next=next;//回復(fù)原先鏈表
cur=next;//cur往后迭代
copyend=copyend->next; //copyend也往后走,如果這個地方不定義copyend或者copyend不往后走的話,我們每次尾插都要重新找尾
}
}
當(dāng)我們理解了這三個步驟后,我們將三個步驟合并一下組成我們最終的代碼:文章來源：http://www.zghlxwxcb.cn/news/detail-420753.html
struct Node* copyRandomList(struct Node* head)
{
struct Node* cur=head;
while(cur)//第一步:拷貝節(jié)點插入原節(jié)點中
{
struct Node* copy=(struct Node*)malloc(sizeof(struct Node));
copy->val=cur->val;
copy->next=cur->next;
cur->next=copy;
cur=copy->next;
}
cur=head;
while(cur)//第二步:將拷貝的節(jié)點的random值確定了
{
struct Node* copy=cur->next;
if(cur->random==NULL)
{
copy->random=NULL;
}
else
{
copy->random=cur->random->next;
}
cur=copy->next;
}
struct Node* copyhead=NULL,*copyend=NULL;
cur=head;
while(cur)//第三步,取下拷貝節(jié)點后尾插
{
if(copyhead==NULL)
{
copyend=copyhead=cur->next;
}
if(copyend->next==NULL)
{
cur=NULL;
}
else{
struct Node* next=copyend->next;
copyend->next=next->next;
cur->next=next;
cur=next;
copyend=copyend->next;
}
}
return copyhead;
}
5. 總結(jié)
雖然我們這一章只分享了三個題目,但是我們可以明顯感受到這個地方的技巧性和思路都是很不好想的,是直接上難度了的.但是我們這個地方使用的快慢指針法和拷貝鏈表的思路是很經(jīng)典的解題思路,第一次做的時候想不到是很正常的,小編第一次做這三道題的時候也是一個有技巧的方法也沒有想到,硬著頭皮去解,解到后面也是報錯一場空.我也是后面去向前輩取經(jīng)得到的思路和方法,所以說我們是站在巨人的肩膀上學(xué)習(xí)編程,自己想不出技巧沒有關(guān)系,消化吸收前輩的經(jīng)驗和技巧也是我們提升自己的方法.我們不斷的做題不斷的總結(jié),下次遇見相似的思路或相似的題我們也就不愁了.這個地方的三個題目需要我們自己畫動態(tài)圖去分析,每一個結(jié)論或是每一個方法想要熟悉它.掌握它都需要我們慢慢畫圖去理解.最后想說,我們到這里才開始真正的去"玩"這個鏈表,我們的鏈表到這里才剛剛開始,各位加油!文章來源地址http://www.zghlxwxcb.cn/news/detail-420753.html
到了這里，關(guān)于面試題思路分享以及延伸問題探討三的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
