程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> [LeetCode]Linked List Cycle II

[LeetCode]Linked List Cycle II

編輯:C++入門知識

[LeetCode]Linked List Cycle II


 

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up:
Can you solve it without using extra space?

首先設圓環的長度為r,距離環口為a時相遇,環外的那一段的距離是b,那麼有2(a+b)=a+b+nr ,n>1;

所以有a+b = nr; 進一步有 b+ pr = (r-a)+qr,即從頭指針和當前相遇位置的指針以相同速度移動一定在環口位置相遇

 

 

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
	public ListNode detectCycle(ListNode head) {
		if(head==null) return null;
		ListNode slow2 = head;
		ListNode slow = head;
		ListNode fast = head;
		boolean isCycle = false;
		while(fast!=null&&fast.next!=null){
			slow = slow.next;
			fast = fast.next.next;			
			if(slow == fast) {
				isCycle =  true;
				break;
			}
		}
		if(isCycle){
			while(slow2!=slow){
				slow = slow.next;
				slow2 = slow2.next;
			}
			return slow;
		}else{
			return null;
		}
	}
}


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved