摘要:由于要比移動的快,如果有環,一定會先進入環,而后進入環。現在問題就簡單了,由于移動的距離永遠是的一般,因此當遍歷玩整個環長度個節點的時候正好遍歷了個節點,也就是說,此時正好指向距離最遠的點。
首先,關于單鏈表中的環,一般涉及到以下問題:
1.給一個單鏈表,判斷其中是否有環的存在;
2.如果存在環,找出環的入口點;
3.如果存在環,求出環上節點的個數;
4.如果存在環,求出鏈表的長度;
5.如果存在環,求出環上距離任意一個節點最遠的點(對面節點);
6.(擴展)如何判斷兩個無環鏈表是否相交;
7.(擴展)如果相交,求出第一個相交的節點;
下面,我將針對上面這七個問題一一給出解釋和相應的代碼。
1.判斷時候有環(鏈表頭指針為head)
對于這個問題我們可以采用“快慢指針”的方法。就是有兩個指針fast和slow,開始的時候兩個指針都指向鏈表頭head,然后在每一步
操作中slow向前走一步即:slow = slow->next,而fast每一步向前兩步即:fast = fast->next->next。
由于fast要比slow移動的快,如果有環,fast一定會先進入環,而slow后進入環。當兩個指針都進入環之后,經過一定步的操作之后
二者一定能夠在環上相遇,并且此時slow還沒有繞環一圈,也就是說一定是在slow走完第一圈之前相遇。證明可以看下圖:
當slow剛進入環時每個指針可能處于上面的情況,接下來slow和fast分別向前走即:
if (slow != NULL && fast->next != NULL) { slow = slow -> next ; fast = fast -> next -> next ; }
也就是說,slow每次向前走一步,fast向前追了兩步,因此每一步操作后fast到slow的距離縮短了1步,這樣繼續下去就會使得
兩者之間的距離逐漸縮小:...、5、4、3、2、1、0 -> 相遇。又因為在同一個環中fast和slow之間的距離不會大于換的長度,因此
到二者相遇的時候slow一定還沒有走完一周(或者正好走完以后,這種情況出現在開始的時候fast和slow都在環的入口處)。
問題1是否存在環的解答
typedef struct node{ char data ; node * next ; }Node; bool exitLoop(Node *head) { Node *fast, *slow ; slow = fast = head ; while (slow != NULL && fast -> next != NULL) { slow = slow -> next ; fast = fast -> next -> next ; if (slow == fast) return true ; } return false ; }
問題2 環的入口點:
從上面的分析知道,當fast和slow相遇時,slow還沒有走完鏈表,假設fast已經在環內循環了n(1<= n)圈。假設slow走了s步,則fast走了2s步,又由于
fast走過的步數 = s + n*r(s + 在環上多走的n圈),則有下面的等式:
2s = s + n ? r;(1)
=> s = n*r;(2)
如果假設整個鏈表的長度是L,入口和相遇點的距離是x(如上圖所示),起點到入口點的距離是a(如上圖所示),則有:
a + x = s = n * r; (3) ?由(2)推出
a + x = (n - 1) r + r ?= (n - 1) r + (L - a) (4) 由環的長度 = 鏈表總長度 - 起點到入口點的距離求出
a = (n - 1) * r + (L -a -x) (5)
從式子(5)以及上圖我們可以看出,從鏈表起點head開始到入口點的距離a,與從slow和fast的相遇點(如圖)到入口點的距離相等。
因此我們就可以分別用一個指針(ptr1, prt2),同時從head與slow和fast的相遇點出發,每一次操作走一步,直到ptr1 == ptr2,此時的位置也就是入口點!
到此第二個問題也已經解決。
Node* findLoopStart(Node *head) { Node *fast, *slow ; slow = fast = head ; while (slow != NULL && fast -> next != NULL) { slow = slow -> next ; fast = fast -> next -> next ; if (slow == fast) break ; } if (slow == NULL || fast -> next == NULL) return NULL ; //沒有環,返回NULL值 Node * ptr1 = head ; //鏈表開始點 Node * ptr2 = slow ; //相遇點 while (ptr1 != ptr2) { ptr1 = ptr1 -> next ; ptr2 = ptr2 -> next ; } return ptr1 ; //找到入口點
第3個問題,如果存在環,求環上節點的個數:
方式1:記錄下相遇節點存入臨時變量tempPtr,然后讓slow(或者fast,都一樣)繼續向前走slow = slow -> next;一直到slow == tempPtr; 此時經過的步數就是環上節點的個數;
方式2: 從相遇點開始slow和fast繼續按照原來的方式向前走slow = slow -> next; fast = fast -> next -> next;直到二者再次項目,此時經過的步數就是環上節點的個數 。
兩種方式本質是一樣的都是在相遇點再次開始走一遍直到再次相遇。
問題4是如果存在環,求出鏈表的長度:
問題二已經知道了起點到入口點的距離,問題三知道了環的長度r;
鏈表長度L = 起點到入口點的距離 + 環的長度r;
問題5是,求出環上距離任意一個節點最遠的點(對面節點)
如下圖所示,點1和4、點2和5、點3和6分別互為”對面節點“ ,也就是換上最遠的點,我們的要求是怎么求出換上任意一個點的最遠點。
對于換上任意的一個點ptr0, 我們要找到它的”對面點“,可以這樣思考:同樣使用上面的快慢指針的方法,讓slow和fast都指向ptr0,每一步都執行與上面相同的操作(slow每次跳一步,fast每次跳兩步),
當fast = ptr0或者fast = prt0->next的時候slow所指向的節點就是ptr0的”對面節點“。
如上圖,我們想像一下,把環從ptro處展開,展開后可以是無限長的(如上在6后重復前面的內容)如上圖。
現在問題就簡單了,由于slow移動的距離永遠是fast的一般,因此當fast遍歷玩整個環長度r個節點的時候slow正好遍歷了r/2個節點,
也就是說,此時正好指向距離ptr0最遠的點。
轉載原文:https://blog.csdn.net/doufei_...
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/31653.html
摘要:既然說到地址空間了就順帶說一下上面環形鏈表這道題的另一種很的解法吧。介紹完常規操作鏈表的一些基本知識點后,現在回到快慢指針。 ??前幾天第一次在 Segmentfault 發文—JavaScript:十大排序的算法思路和代碼實現,發現大家似乎挺喜歡算法的,所以今天再分享一篇前兩個星期寫的 Leetcode 刷題總結,希望對大家能有所幫助。 ??本文首發于我的blog 前言 ??今天終于...
摘要:鏈式存儲結構的線性表將采用一組任意的存儲單元存放線性表中的數據元素。三單向鏈表的實現下面的程序分別實現了線性表的初始化獲取線性表長度獲取指定索引處元素根據值查找插入刪除清空等操作。 文章有不當之處,歡迎指正,如果喜歡微信閱讀,你也可以關注我的微信公眾號:好好學java,獲取優質學習資源。 一、概述 單向鏈表(單鏈表)是鏈表的一種,其特點是鏈表的鏈接方向是單向的,對鏈表的訪問要通過順序讀...
閱讀 2410·2021-11-19 09:40
閱讀 3575·2021-10-12 10:12
閱讀 1884·2021-09-22 15:04
閱讀 2898·2021-09-02 09:53
閱讀 762·2019-08-29 11:03
閱讀 1122·2019-08-28 18:11
閱讀 1724·2019-08-23 15:28
閱讀 3580·2019-08-23 15:05