2022/05/01

Leetcode Note: Go - Linked List Cycle

Linked List Cycle - LeetCode
https://leetcode.com/problems/linked-list-cycle/

  • Go 言語で取り組んだメモ

所感

  • Linked List がサイクルを持つか判定する

回答

[Golang] slow and fast pointer method, Time: O(n), Space: O(1) - LeetCode Discuss
https://leetcode.com/problems/linked-list-cycle/discuss/1355291/Golang-slow-and-fast-pointer-method-Time%3A-O(n)-Space%3A-O(1)

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func hasCycle(head *ListNode) bool {
    slow := head
    fast := head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            return true
        }
    }
    return false
}
  • init:
    • slow => head で初期化
    • fast => head で初期化
  • loop: fast と fast.Next が nil では無ければ継続
    • slow に slow.Next を代入
    • fast に fast.Next.Next を代入
    • slow と fast が等価なら return true
  • return false
  • loop の回し方がトリッキーだが slow, fast に Next を代入していくことで、継続的に Linked List を回している

See Also