JZ23 鏈表中環的入口結點
描述
給一個長度為n鏈表，若其中包含環，請找出該鏈表的環的入口結點，否則，回傳null，
決議
環很大
在前面我們提到過快慢指標，判斷是否有環，如果有環，在來找環的入口，如果沒環直接回傳null即可，我們假設是有環的，那么會有兩種情況，一種是O型，一種是6型，其實原理都一樣，這里主要看一下6字型的環，他會有兩種情況，
如果有環，那么快指標走過的路徑就是圖中a+b+c+b，慢指標走過的路徑就是圖中a+b，因為在相同的時間內，快指標走過的路徑是慢指標的2倍，所以這里有a+b+c+b=2*(a+b)，整理得到a=c
在相遇的時候再使用兩個指標，一個從鏈表起始點開始，一個從相遇點開始，每次他們都走一步，直到再次相遇，那么這個相遇點就是環的入口，
環很小
這種情況下當快慢指標在環上相遇的時候，快指標有可能在環上轉了好幾圈，我們假設相遇的時候快指標已經在環上轉了n圈，
那么相遇的時候快指標走過的路徑就是a+b+(b+c)*n，（b+c其實就是環的長度），慢指標走過的路徑是a+b，由于相同時間內快指標走過的路徑是慢指標的2倍，
所以有a+b+(b+c)n=2(a+b)，整理得到a+b=n*(b+c)，也就是說a+b等于n個環的長度，
我們還可以使用兩個指標，一個從鏈表的起點開始，一個從相遇點開始，那么就會出現一種情況就是，一個指標在路徑a上走，一個指標一直在環上轉圈，最侄訓走到第一種情況，
代碼
package mid.JZ23鏈表中環的入口結點;
class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead) {
ListNode slow = hasCycle(pHead);
if (slow == null) return null;
//快的回到起點
ListNode fast = pHead;
while(fast != slow) {
fast = fast.next;
slow = slow.next;
}
return fast;
}
/**
* 判斷鏈表是否有環
* @param head
* @return
*/
public ListNode hasCycle(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) return slow;
}
return null;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/539015.html
標籤：其他