[LeetCode] 142. Linked List Cycle II

轉自LeetCode

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

Note: Do not modify the linked list.

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

<Solution>
這題是 Linked List Cycle 的衍生題

這類型的題目，其實有一個著名的演算法，叫 Floyd's Cycle Detection Algorithm

可以用來處理三個問題

(1) 判斷是否有 cycle

(2) 找到 cycle 的起始點

(3) 找出 cycle 的長度

這題可以基於 Linked List Cycle 的解法，再多一些步驟就可以解出來了

想法如下

• 如果判斷出有 cycle 的話，將 oneStep 移回 list 的起點，然後 oneStep 和 twoStep 這兩個指標每次都只往前移動一步，再次相遇的那個點就是 cycle 的起點

code  如下
c++

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	ListNode *detectCycle(ListNode *head) {
	ListNode *oneStep = head;
	ListNode *twoStep = head;
	//>> find a cycle
	while(twoStep && twoStep->next) {
	oneStep = oneStep->next;
	twoStep = twoStep->next->next;
	if(oneStep == twoStep) {
	break;
	}
	}
	//>> there is no cycle
	if(!twoStep || !twoStep->next) {
	return NULL;
	}
	//>> find the start node of cycle
	oneStep = head;
	while(oneStep != twoStep) {
	oneStep = oneStep->next;
	twoStep = twoStep->next;
	}
	return twoStep;
	}
	};

view raw findLinkedListCycleStartPoint.cpp hosted with ❤ by GitHub

kotlin

	/**
	* Example:
	* var li = ListNode(5)
	* var v = li.`val`
	* Definition for singly-linked list.
	* class ListNode(var `val`: Int) {
	* var next: ListNode? = null
	* }
	*/
	class Solution {
	fun detectCycle(head: ListNode?): ListNode? {
	var slow = head
	var fast = head
	while(fast != null && fast!!.next != null) {
	slow = slow?.next
	fast = fast?.next?.next
	if(slow == fast) {
	break
	}
	}
	if(fast == null || fast!!.next == null) {
	return null
	}
	slow = head
	while(slow != fast) {
	slow = slow?.next
	fast = fast?.next
	}
	return slow
	}
	}

view raw linked_list_cycle_II.kt hosted with ❤ by GitHub