分類  >  編程 >

單鏈表的環相關有關問題

tags:    時間:2014-05-04 18:39:35
單鏈表的環相關問題

給定一個單鏈表,只給出頭指針h:

1、 如何判斷是否存在環?

證明:


 slow首次在A點進入環路時,fast一定在環中的B點某處。設此時slow距head長為x,B點距A點長度為y,環周長為s。因為fast和slow的步差為1,所以slow前行距離為y的時候,恰好會被fast在M點追上。因為y<s,所以slow尚未完成一次遍歷。

//判斷單鏈表是否有環 	public static boolean hasCycle(ListNode head) { 		if(head == null || head.next == null){ 			return false; 		} 		ListNode slow = head; 		ListNode fast = head; 		while(fast.next != null && fast.next.next != null){ 			fast = fast.next.next; 			slow = slow.next; 			if(fast == slow){ 				return true; 			} 		} 		return false;     }

2、 如何知道環的長度?

證明:(有公式所以截圖了)


//返迴環的長度 	public static int cycleLength(ListNode head) { 		if(head == null || head.next == null){ 			return 0; 		} 		ListNode slow = head; 		ListNode fast = head; 		while(fast.next != null && fast.next.next != null){ 			fast = fast.next.next; 			slow = slow.next; 			if(fast == slow){ 				fast = fast.next.next; 				int length = 2; 				while(fast != slow){ 					fast = fast.next.next; 					length = length + 2; 				} 				return length; 			} 		} 		return 0; } 

3、 如何找出環的連接點在哪裡?

證明:在fast和slow第一次相遇的時候,假定slow走了n步驟,環路的入口是在x步的時候經過的,那麼有

slow走的路徑: x+y = n;   y為fast和slow相交點M距離環路入口的距離

fast走的路徑: x+y+k*s = 2*n;   s為環路的周長,k是整數

所以得出 n = k*s;

顯然,如果從x+y點開始,slow再走n步的話,還可以回到x+y這個點(繞了k圈)

同時另一個指針temp從頭開始走的話,經過n步,也會達到x+y這點

兩者都減去y步,可知兩者走x步必然會在環路的入口點處相遇

//找出環的起始點在哪裡 		public static ListNode getCycleStartNode(ListNode head) { 			if(head == null || head.next == null){ 				return null; 			} 			ListNode slow = head; 			ListNode fast = head; 			while(fast.next != null && fast.next.next != null){ 				fast = fast.next.next; 				slow = slow.next; 				if(fast == slow){ 					fast = head; 					while(fast != slow){ 						fast = fast.next; 						slow = slow.next; 					} 					return slow; 				} 			} 			return null; 	    } 

4、帶環鏈表的長度是多少?

證明:總長度 = s + x;

//帶環鏈表總長度,0表示沒環 		public static int getListLength(ListNode head) { 			if(head == null || head.next == null){ 				return 0; 			} 			ListNode slow = head; 			ListNode fast = head; 			while(fast.next != null && fast.next.next != null){ 				fast = fast.next.next; 				slow = slow.next; 				if(fast == slow){ 					ListNode p = slow;//標記相遇的地方 					fast = head; 					int lengthX = 0; 					int lengthS = 0; 					while(fast != slow){ 						fast = fast.next; 						slow = slow.next; 						lengthX++; 					} 					lengthS = lengthX; 					while(slow != p){ 						slow = slow.next; 						lengthS++; 					} 					return lengthX+lengthS; 				} 			} 			return 0; 	    } 





推薦閱讀文章

Bookmark the permalink ,來源:互聯網