【解題筆記 - JS】Node 找到循環鍊的長度

閱讀時間約 6 分鐘

Node 對我來說一直是很似懂非懂的概念,題型有樹狀、鏈節等。因為沒有實際可見的數字或字串等實物可以觀察中間步驟,所以比起其他解題抽象許多。如果光是查找 Node 各型定義還是不好理解,要怎麼使用這些知識連結解題方法。所以我認為有圖解步驟輔助,會是比較容易理解的步驟。

以下解題方法來自網友與 GPT 提供的答案,我想在本文中嘗試自己做視覺化圖解,說明 CodeWars 5kyu - Can you get the loop ? 的解題思路。


題目資訊

  • 題目來源:https://www.codewars.com/kata/52a89c2ea8ddc5547a000863
  • 題目說明:
    給您一個作為鍊錶開頭的節點。此清單包含一個懸掛塊和一個循環。您的目標是確定循環的長度。您可以使用 node.getNext()node.next 這兩個方法走入下一個節點。
    ※ 環長就是下圖中紫色的區塊


先前我一直很糾結於上圖,以為一定要找到環與鏈的交接處,再從倒數第一個環中的節點取得環的長度。看過別人的解答後,才脫離得先找到環的起始點這個想法。


解題思路

建立鏈節概念

鏈節初始狀態的可能性:有可能只有一個節,或是一條鏈卻沒有成環形。也可能有鏈有環,或是只有環型的狀況。我們不知道目前拿到的鏈結是什麼型態,所以我們要先可以拆解兩個理解的步驟:
Q1. 是否有環
Q2. 判斷環有多長
先有這個想像會比較容易理解後續。

鏈的可能性

鏈的可能性


常見的長短針解法

Q1. 長短針解法:理解「是否有環」的概念

就像是我們的時鐘,時針和分針的走路不一。如果這兩只針在走速不一的狀態下,仍有交疊處,就代表他們的行走路徑能成為一個環型。

如果還有點模糊,稍等一下,待會我們可以從下圖的示例 2、3 來驗證這個概念。


Q2. 視覺化長短針解法:環的長度

下圖是上面提到鏈節的幾種初始狀態可能,在使用長短針解法時的運行方式。

  1. 假設有兩只針,快針(紅色 F) 慢針(綠色 S),長短針一但走入環型範圍,就只會在環形內部環繞繼續行走。若無法前進則停止。
    - 快針:每次走 2 個節點。
    - 慢針:每次走 1 個節點。
    - 數字標示:第 n 步。
    - 橘黃色圈圈:兩只針在環繞環形多次後的交疊處。
  2. 示例 2:有以上概念後,我們可以從示例 2 回推先前提到「如果這兩只針在走速不一的狀態下,仍有交疊處,就代表他們的行走路徑能成為一個環型」這句話。
    當只有鏈沒有環的狀態下,兩針走到無法再行進下一步時就會停止。
    - 慢針(綠色 S)在第 2 步是可以站在節點上的。
    - 快針(紅色 F)在第 1 步位置就已經超過慢針的第 1 步,並且當慢針也抵達相同位置時,但快針卻已經沒有下兩格可以前進所以止步。因為沒有環,所以環長為 0,0 是要返回的答案。
  3. 示例 3:假設題目給我們的是有鏈也有環的鏈結。
    - 慢針(綠色 S)快針(紅色 F)在第 3 步會在相同節點上相遇,3 即是我們要返回的答案。
  4. 示例 4:示例 4 中,慢針(綠色 S)快針(紅色 F)在第 6 步會在相同節點上相遇。若環的長度再做調整,引用上述「長短針一但走入環型範圍,就只會在環形內部環繞繼續行走」的概念,快慢針可能會在走環狀第 n 圈的時候才相遇。總之只要有環就一定會相遇。(例如時鐘時針和分針一天會相遇 24 次)。
長短針解法

長短針解法


解題程式碼

延伸上面圖解的概念,可以以此來實作題目,先判斷是否有環,再取得環的長度

1. 設定快慢針

  • 起始點為 node
  • 慢針:slow,每次使用 getNext() 走 1 格節點。
  • 快針:fast,每次使用兩次的 getNext() ,共計走 2 格節點。

2. 判斷是否有環

  • 帶入情境,如果沒有節點,或無法前進,直接 return 0
  • 每次移動,都判斷兩針所處位置是否同值。若兩針跑完迴圈始終不相等,也 return 0
  • 如果兩針有同值,代表這是一個有環的鏈表。讓我們進入「取得環的長度」的步驟。

3. 取得環的長度

  • Step 2 中的 while (fast && fast.getNext()),如果有找到同值,兩針所處的位置就會停在交叉點上,然後跳入 Step 3 的步驟。
  • 將慢針停止不動,將快針 fast 改為每次只走 1 格,當快針再次回到出發點(與慢針的交差點),就是環型的長度。
function loop_size(node) {	
//如果沒有節點,或是節點只有一個(也就是 node.getNext() 無法取值),則返回 0,因為一定無法成環形
if (!node || !node.getNext()) {
return 0;
}

/* Step 1 建立環形交集點 */
//如果有環形,可以用時鐘長短針的概念來看,先建立快針與慢針
let slow = node;
let fast = node;

/* Step 2 建立環形交集點 */
//當快針當前狀態能取值,並且快針下一格也存在,則迴圈成立
//慢針每次走一格,快針每次走兩格,如果快針和慢針得到同值,則提早離開迴圈
while (fast && fast.getNext()) {
slow = slow.getNext();
fast = fast.getNext().getNext();
if (slow === fast) {
break;
}
}

// 如果迴圈停止時,fast 和 slow 不相等
if (slow !== fast) {
return 0;
}

// Step 3: 固定兩針起始點為同一個點,將快針速度改為每次一格,回到原點的迴圈次數表環型長度
let count = 1;
fast = fast.getNext();
while (fast !== slow) {
fast = fast.getNext();
count++;
}

return count;
}


延伸

14會員
20內容數
從藝術領域轉職到前端工程師,喜歡書寫學習歷程和技術文件,掌握經驗與隨時提取的感覺很好。
留言0
查看全部
發表第一個留言支持創作者!
Ann Chou的沙龍 的其他內容
JavaScript 套件,頁碼 Pagination.js 搭配 axios API 請求範例
分享這套功能齊全,視覺超級可愛還有響應式變化,教學文件又很容易閱讀的套件 Evo Calendar。 當初在製作 JS side project 時,想找一個與 VCalendar 視覺相近的套件,但多半都不合意。六角學院指派的 side project 教練也幫我找了另一個純 JS 的範例,也很
不喜歡 HTML 原生的時間選擇器外型嗎?試試看 flatpickr.js 吧! 以下是使用 flatpickr 做簡單的示例,以及 flatpickr 使用注意事項。
我依舊維持著修習 JS 的步伐,但我仍然覺得自己對 JS 的熟悉度不足。在 JS 班開課後,我藉由刷題庫和做 side project 專題,填補了課前的不自信感和知識焦慮。最終我們小組在 2.5 個月內開發了一個訂閱制電商網站的前後台,我也參加了 F2E week1 完賽,獲得銀級徽章
這是我參加為期三個月的六角學院 2023 網頁前端切版直播班中的學習和成長經驗。最初參加直播班時誤以為自己已經具備足夠的前端知識,但後來發現自己的程式碼還有改進的空間。我在參與直播班的過程中,不僅學到了更多切版技術,也在小組協作中體驗到了組織能力和團隊合作的重要性,並從做設計稿與切版中發現個人優勢。
軟工體驗營最後一周,短短一個月的前端程式體驗,真的是非常超值的課程。不論是檢視自己對寫程式的感受,或是透過社群認識自己的新面向、軟實力的培養都是。六角是非常新手友善的程式學校,推薦給每位想學習前端的初心者朋友。
JavaScript 套件,頁碼 Pagination.js 搭配 axios API 請求範例
分享這套功能齊全,視覺超級可愛還有響應式變化,教學文件又很容易閱讀的套件 Evo Calendar。 當初在製作 JS side project 時,想找一個與 VCalendar 視覺相近的套件,但多半都不合意。六角學院指派的 side project 教練也幫我找了另一個純 JS 的範例,也很
不喜歡 HTML 原生的時間選擇器外型嗎?試試看 flatpickr.js 吧! 以下是使用 flatpickr 做簡單的示例,以及 flatpickr 使用注意事項。
我依舊維持著修習 JS 的步伐,但我仍然覺得自己對 JS 的熟悉度不足。在 JS 班開課後,我藉由刷題庫和做 side project 專題,填補了課前的不自信感和知識焦慮。最終我們小組在 2.5 個月內開發了一個訂閱制電商網站的前後台,我也參加了 F2E week1 完賽,獲得銀級徽章
這是我參加為期三個月的六角學院 2023 網頁前端切版直播班中的學習和成長經驗。最初參加直播班時誤以為自己已經具備足夠的前端知識,但後來發現自己的程式碼還有改進的空間。我在參與直播班的過程中,不僅學到了更多切版技術,也在小組協作中體驗到了組織能力和團隊合作的重要性,並從做設計稿與切版中發現個人優勢。
軟工體驗營最後一周,短短一個月的前端程式體驗,真的是非常超值的課程。不論是檢視自己對寫程式的感受,或是透過社群認識自己的新面向、軟實力的培養都是。六角是非常新手友善的程式學校,推薦給每位想學習前端的初心者朋友。
你可能也想看
Google News 追蹤
Thumbnail
接下來第二部分我們持續討論美國總統大選如何佈局, 以及選前一週到年底的操作策略建議 分析兩位候選人政策利多/ 利空的板塊和股票
Thumbnail
🤔為什麼團長的能力是死亡筆記本? 🤔為什麼像是死亡筆記本呢? 🤨作者巧思-讓妮翁死亡合理的幾個伏筆
Thumbnail
我們的思維常常呈現網狀結構,涉及大量相關訊息,表達和行動需要線性思維,而網狀思維與線性思維不相匹配,中間隔著關鍵的一步,即讓網狀思維變得有邏輯和組織。 金字塔原理的核心價值就在於找到一套系統方法,建構一個層級清晰、邏輯清晰的樹狀思維。 只有完成這一步,從思考到表達、從思考到行動的道路才算是完整的。
Thumbnail
書名: 別再扯自己後腿了:全美最佳精神科醫師 教你戰勝自我挫敗,解決各種難題 作者: 馬克.葛斯登, 菲利浦.高德堡  ISBN/ISSN:9789861755779
Thumbnail
上一篇講了『麥肯錫最強問題解決法』一書中有關『問題分解』的內容,這一篇要談『問題分析』的部分,這邊再複習一下書中所列出的『七步驟』:『定義問題』,『分解』,『排序』,『計畫』,『分析』,『統合』,『溝通』。
Thumbnail
現在許多職能之所以稀缺較難以取代,就在於這些職能並非只是日常規律性的操作行為,而是能解決問題,解決某些人的痛點。醫師解決人健康上的問題,產品設計者解決消費者需求方面的問題,工程師解決技術進展上的問題,等等,這都圍繞在解決問題這個核心技能上。 本書提供更高層次的分析與解決問題流程。
Thumbnail
報考培訓飛行員的基本關卡,還有包含多益的口說寫作測驗。本篇文章分享多益口說五大題的模板、技巧以及解題攻略,希望能在考試的道路上,助讀者一臂之力!
★有時面對複雜的問題,答案其實很簡單。 ●你可以做任何事,但是不能做所有的事。至少不是在同一時間進行。 ●抱持「少即是多」的態度,設定數量少一些但意義多一些的目標,面對人生、工作及一切,就會珍惜已經擁有的一切。 ●當時間的投資者,而非時間的管理者。
★我們要學會運用邏輯思考,去洞悉問題的本質。所謂洞悉本質,就是分析問題的真正原因所在,並找出正確的解決方法,進而解決問題。從這個角度看,問題解決的前提就是洞悉問題的本質。 ●一個問題如果真想得到終極解決,光靠歸納表面現象和解決表面問題是絕對做不到的,關鍵要推測出事情的本源。
Thumbnail
閱讀筆記(97)《造局者》引領時代者,屬於正在解決未來的問題   一般的管理者,看到問題解決問題;   優秀的管理者,解決現在的潛在問題;   頂尖的管理者,佈局未來將到來的問題。 上述的三條,是過去在讀管理大師杜拉克(Peter Drucker)所收穫到的感悟。 對應到這時代裡,能夠創造未
Thumbnail
接下來第二部分我們持續討論美國總統大選如何佈局, 以及選前一週到年底的操作策略建議 分析兩位候選人政策利多/ 利空的板塊和股票
Thumbnail
🤔為什麼團長的能力是死亡筆記本? 🤔為什麼像是死亡筆記本呢? 🤨作者巧思-讓妮翁死亡合理的幾個伏筆
Thumbnail
我們的思維常常呈現網狀結構,涉及大量相關訊息,表達和行動需要線性思維,而網狀思維與線性思維不相匹配,中間隔著關鍵的一步,即讓網狀思維變得有邏輯和組織。 金字塔原理的核心價值就在於找到一套系統方法,建構一個層級清晰、邏輯清晰的樹狀思維。 只有完成這一步,從思考到表達、從思考到行動的道路才算是完整的。
Thumbnail
書名: 別再扯自己後腿了:全美最佳精神科醫師 教你戰勝自我挫敗,解決各種難題 作者: 馬克.葛斯登, 菲利浦.高德堡  ISBN/ISSN:9789861755779
Thumbnail
上一篇講了『麥肯錫最強問題解決法』一書中有關『問題分解』的內容,這一篇要談『問題分析』的部分,這邊再複習一下書中所列出的『七步驟』:『定義問題』,『分解』,『排序』,『計畫』,『分析』,『統合』,『溝通』。
Thumbnail
現在許多職能之所以稀缺較難以取代,就在於這些職能並非只是日常規律性的操作行為,而是能解決問題,解決某些人的痛點。醫師解決人健康上的問題,產品設計者解決消費者需求方面的問題,工程師解決技術進展上的問題,等等,這都圍繞在解決問題這個核心技能上。 本書提供更高層次的分析與解決問題流程。
Thumbnail
報考培訓飛行員的基本關卡,還有包含多益的口說寫作測驗。本篇文章分享多益口說五大題的模板、技巧以及解題攻略,希望能在考試的道路上,助讀者一臂之力!
★有時面對複雜的問題,答案其實很簡單。 ●你可以做任何事,但是不能做所有的事。至少不是在同一時間進行。 ●抱持「少即是多」的態度,設定數量少一些但意義多一些的目標,面對人生、工作及一切,就會珍惜已經擁有的一切。 ●當時間的投資者,而非時間的管理者。
★我們要學會運用邏輯思考,去洞悉問題的本質。所謂洞悉本質,就是分析問題的真正原因所在,並找出正確的解決方法,進而解決問題。從這個角度看,問題解決的前提就是洞悉問題的本質。 ●一個問題如果真想得到終極解決,光靠歸納表面現象和解決表面問題是絕對做不到的,關鍵要推測出事情的本源。
Thumbnail
閱讀筆記(97)《造局者》引領時代者,屬於正在解決未來的問題   一般的管理者,看到問題解決問題;   優秀的管理者,解決現在的潛在問題;   頂尖的管理者,佈局未來將到來的問題。 上述的三條,是過去在讀管理大師杜拉克(Peter Drucker)所收穫到的感悟。 對應到這時代裡,能夠創造未