CCI2.6尋找有環鏈表環路的開頭節點

給定一個有環鏈表，實現以算法返回環路的開頭結點。 有環鏈表的定義 在鏈表中某個節點的next元素指向它前面出現過的節點，則表明該鏈表存在環路。 示例 輸入：A-B-C-D-E-C(C節點出現兩次) 輸出：C 分析 ： 1，快慢指針法判斷鏈表是否有環 fast每次前移兩步，

給定一個有環鏈表，實現以算法返回環路的開頭結點。

有環鏈表的定義

在鏈表中某個節點的next元素指向它前面出現過的節點，則表明該鏈表存在環路。

示例

輸入：A->B->C->D->E->C(C節點出現兩次)

輸出：C

分析：

1，快慢指針法判斷鏈表是否有環

fast每次前移兩步，slow每次前移一步，兩指針若能相遇，則有環，否則沒有環。

2，假設鏈表頭到環頭移動k步，slow指向環頭的時候，fast移動了2*k步，此時兩者相距k步，也可以認為快指針再過m*size-k步之后追上慢指針。當兩者相遇的時候，則慢指針距離環頭還有k步。因為此時不知道k的具體大小，但是知道k是鏈表頭到環頭的步數，讓fast指向鏈表頭，之后快慢指針每次往后移動一步，兩者相遇的地方就是環頭。

package test;

public class FindLoopStart {
	public Node findLoopStart(Node head){
	Node fast = head;
	Node slow = head;
	while(fast!=null || fast.next!=null){
	fast = fast.next.next;
	slow = slow.next;
	if(fast == slow)
	break;
	}
	//沒有環則返回null
	if(fast==null || fast.next==null)
	return null;
	//相遇之后，slow節點再走k步達到環開頭
	//此時，并不知道k的具體值，但是知道k是從鏈表開頭到環頭的步數
	//于是，讓fast指向鏈表頭，每次往后移一步，則再次相遇的時候，走的步數就是k
	//則相遇地點就是環的開頭
	fast = head;
	while(fast != slow){
	fast = fast.next;
	slow = slow.next;
	}
	return slow;
	}
}

聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com