leetcode
January 8, 2024

Viiisit [LeetCode] - 141. Linked List Cycle

#php#javascript#ruby

keep learning, keep coding!

Problem - Linked List Cycle

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

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

翻譯蒟蒻

判斷一個單向鏈表（linked list）是否包含循環。在鏈表中，每個節點都包含一個指向下一個節點的指針。如果在這個鏈表中有一個循環，就可以從某個節點開始，按照指針的方向一直遍歷，最終又回到某一個之前到過的節點。解這個問題的一種常見方法是使用兩個指針，一個快指針和一個慢指針，來追蹤鏈表。如果鏈表中存在循環，快指針最終會追上慢指針。

檢查一個鏈表是否有循環。
使用兩個指標，一個 fast 快指針（每次移動兩步）和一個 slow 慢指針（每次移動一步）。如果鏈表有循環，那麼 fast 快指針最終將追趕上 slow 慢指針，也就是 fast == slow 時，返回 true。如果鏈表沒有循環，那麼 fast 快指針會到鏈表的結尾，返回 false。

Solution - JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {    
    if (head === null) {
        return false;
    }
    let slow = head;
    let fast = head.next;
    while (slow !== fast) {
        if (fast === null || fast.next === null) {
            return false;
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    return true;
};

Solution - Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
def hasCycle(head)
    return false if head.nil?
    slow = head
    fast = head.next

    while slow != fast
        return false if fast.nil? || fast.next.nil?
        slow = slow.next
        fast = fast.next.next
    end

    return true
end

Solution - PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function hasCycle($head) {
    if ($head === null) {
        return false;
    }
    $slow = $head;
    $fast = $head->next;
    while ($slow !== $fast) {
        if ($fast === null || $fast->next === null) {
            return false;
        }
        $slow = $slow->next;
        $fast = $fast->next->next;
    }
    return true;
}

LeetCode 傳送門 - Linked List Cycle