CCI2.6尋找有環(huán)鏈表環(huán)路的開頭節(jié)點(diǎn)

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

給定一個(gè)有環(huán)鏈表，實(shí)現(xiàn)以算法返回環(huán)路的開頭結(jié)點(diǎn)。

有環(huán)鏈表的定義

在鏈表中某個(gè)節(jié)點(diǎn)的next元素指向它前面出現(xiàn)過的節(jié)點(diǎn)，則表明該鏈表存在環(huán)路。

示例

輸入：A->B->C->D->E->C(C節(jié)點(diǎn)出現(xiàn)兩次)

輸出：C

分析：

1，快慢指針法判斷鏈表是否有環(huán)

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

2，假設(shè)鏈表頭到環(huán)頭移動(dòng)k步，slow指向環(huán)頭的時(shí)候，fast移動(dòng)了2*k步，此時(shí)兩者相距k步，也可以認(rèn)為快指針再過m*size-k步之后追上慢指針。當(dāng)兩者相遇的時(shí)候，則慢指針距離環(huán)頭還有k步。因?yàn)榇藭r(shí)不知道k的具體大小，但是知道k是鏈表頭到環(huán)頭的步數(shù)，讓fast指向鏈表頭，之后快慢指針每次往后移動(dòng)一步，兩者相遇的地方就是環(huán)頭。

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;
	}
	//沒有環(huán)則返回null
	if(fast==null || fast.next==null)
	return null;
	//相遇之后，slow節(jié)點(diǎn)再走k步達(dá)到環(huán)開頭
	//此時(shí)，并不知道k的具體值，但是知道k是從鏈表開頭到環(huán)頭的步數(shù)
	//于是，讓fast指向鏈表頭，每次往后移一步，則再次相遇的時(shí)候，走的步數(shù)就是k
	//則相遇地點(diǎn)就是環(huán)的開頭
	fast = head;
	while(fast != slow){
	fast = fast.next;
	slow = slow.next;
	}
	return slow;
	}
}

聲明：本網(wǎng)頁內(nèi)容旨在傳播知識(shí)，若有侵權(quán)等問題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com