142#環形鏈表2

來自專欄 Leetcode刷題之路

題目描述

142#環形鏈表2

給定一個鏈表，返回鏈表開始入環的第一個節點。 如果鏈表無環，則返回 null。

說明：不允許修改給定的鏈表。

進階： 你是否可以不用額外空間解決此題？

分析

使用雙指針可以解決該問題。

• 鏈表沒有環的判定可以參考第141題，環形鏈表。

現在在鏈表有環的情況下分析。設一個快指針和一個慢指針，這兩個指針的初始位置都在head，慢指針移動速度為1，快指針是它的兩倍。

如圖，設從head到環形開始結點的距離是A，慢指針從環形開始結點走到相遇點走過的路程是B，環的長度是L（畫圖的時候漏掉了，圖中沒有標示出來）。於是有：

• 對慢指針，從head走到meet的距離為A+B
• 對快指針，從head走到meet的距離為2A+2B（因為快指針的速度是慢指針的兩倍，而在相遇時它們走了相同的時間）
• 相遇時，慢指針被快指針套了一圈，即快指針比慢指針多走一圈

根據以上分析我們可以列一個等式：A+B+L = 2A+2B，可以解得L = A + B。從這個結果可以看出，meet到begin的距離也是A。這意味著，如果我們分別放兩個指針在head和meet，讓它們以相同的速度前進，它們第一次相遇的地方就是我們要找的環形開始結點。

源碼

/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */public class Solution { public ListNode detectCycle(ListNode head) { if (head == null) return null; ListNode fast = head; ListNode slow = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if (fast == slow) { slow = head; while (slow != fast) { slow = slow.next; fast = fast.next; } return slow; } } return null; }}

推薦閱讀：