leetcode javascript版 142. 環形連結清單 II

目錄

• • 方法一：利用空間
  • 方法二：快慢指針

方法一：利用空間

周遊連結清單，對于每個節點對象，新增屬性isVisited = true。同時每次周遊判斷下一個節點是否擁有isVisited屬性，如果有那麼下一個節點就是入環的第一個節點。

1. 時間複雜度O(n)
2. 空間複雜度O(n)

var hasCycle = function(head) {
	var curr = head;
	while(curr != null) {
	    if(curr.next == null) {
	        return false;
	    }
	    if(curr.next.isCheck) {
	        return curr.next;
	    } else {
	        curr.isCheck = true;
	        curr = curr.next;
	    }
	}
	return false;
};
           

方法二：快慢指針

用兩個指針同時周遊連結清單，快指針每次走兩步，慢指針每次走一步。如果連結清單中有環，那麼他們終将相遇。可證：自他們相遇後，指針1從起點每次走一步，指針2從相遇點每次走一步，指針1和指針2相遇處就是環的起點。證明如下：

如下圖，設Y點為環起點，Z點為快慢指針相遇點，abc為這幾個關鍵節點間的路程（可能包括很多節點）。

因為，相遇時快指針走過的路程肯定為慢指針走過的路程的2倍。得：

(a+b)2 = a+b+(b+c)n //n>=1，n為快指針在相遇前繞環的圈數

解方程得 a = (b+c)(n-1)+c

是以：

當n=1時，a=c

當n>1時，a=c+n圈

得證。

1. 時間複雜度O(n)
2. 空間複雜度O(1)

var hasCycle = function(head) {
   var p1 = head;
   var p2 = head;
   while(p2 !== null && p2.next !== null) {
   	p1 = p1.next;
   	p2 = p2.next.next;
   	if(p1 === p2) { //判斷有環
   		p1 = head;  //p1從頭開始每次走一步，p2從相遇處開始每次走一步
   		while(p1 != p2) {
   			p1 = p1.next;
   			p2 = p2.next;
   		}
   	return p1;
   	}
   }
   return false;
};