題目

https://leetcode.com/problems/linked-list-cycle/

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

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, 
where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, 
where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Follow up:

Can you solve it using O(1) (i.e. constant) memory?

解答

C#

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public bool HasCycle(ListNode head)
    {
        try
        {
            if (head == null)
                return false;

            var oneStep = head;
            var twoStep = head;
            while (oneStep.next != null && twoStep.next != null)
            {
                oneStep = oneStep.next;
                twoStep = twoStep.next.next;
                if (oneStep == twoStep)
                    return true;
            }
            return false;
        }
        catch (Exception)
        {
            return false;
        }
    }
}

結果

Runtime: 88 ms, faster than 99.75% of C# online submissions.

Memory Usage: 24.8 MB, less than 7.14% of C# online submissions.

Time Complexity: O(n)

Space Complextiy: O(1)

為什麼我要這樣做？

不知道大家對於 LinkedList 有沒有印象？這是我昨天有提到的資料結構
趁著大家有印象的時候，又找了一題跟 LinkedList 有關的題目

忘記的人請參考↓
[Day 14] 演算法刷題 LeetCode 21. Merge Two Sorted Lists (Easy)

這題是要判斷輸入的 ListNode 是不是一個 cycle，換句話說就是 next node 永遠不會是 null

1. 宣告 oneStep，它永遠只會一步一步向前走 ，似魔鬼的步伐
2. 宣告 twoStep，它一次會走兩步
3. while 迴圈
   • 只要確定 oneStep 的 next node 不是 null， twoStep 的 next node 也不是 null 的話
     • oneStep 還是一步一步向前走
     • twoStep 還是兩步兩步向前走
     • 它們總有一天會相撞 (修度A丟) ，就代表 是 一個 cycle list，並return true
   • 若兩者其中之一的 next node 為 null，就代表 不是 cycle list，並return false
4. Error handling，以防出現 Runtime Exception，並return false

示意圖

如果看文字敘述不是很明確的話，可以看下面的示意圖。

以上就是這次 LeetCode 刷題的分享啦！
如果其它人有更棒的想法及意見，請留言或寄信(t4730@yahoo.com.tw) 給我。
那我們就下回見囉