[LeetCode] 141. Linked List Cycle

Given a linked list, determine if it has a cycle in it.

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

<Solution>

這題是要判斷 linked list 是否有迴圈

想法如下

• 準備兩個指標，一個每次只往前一步，一個每次往前兩步

• 如果有迴圈的話，兩個指標就會重疊

code 如下
c++

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	bool hasCycle(ListNode *head) {
	ListNode *oneStep = head;
	ListNode *twoStep = head;
	while(twoStep && twoStep->next) {
	oneStep = oneStep->next;
	twoStep = twoStep->next->next;
	if(oneStep == twoStep) {
	return true;
	}
	}
	return false;
	}
	};

view raw findLinkedListCycle_1.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 hasCycle(head: ListNode?): Boolean {
	var slow = head
	var fast = head
	while(fast != null && fast!!.next != null) {
	slow = slow?.next
	fast = fast?.next?.next
	if(slow == fast) {
	return true
	}
	}
	return false
	}
	}

view raw linked_list_cycle.kt hosted with ❤ by GitHub

後續補充

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

可以處理三個問題

(1) 判斷有沒有 cycle

(2) 找到 cycle 的起點

(3) 找出 cycle 的長度