141.linked-list-cycle.go

/*
 * @lc app=leetcode id=141 lang=golang
 *
 * [141] Linked List Cycle
 *
 * https://leetcode.com/problems/linked-list-cycle/description/
 *
 * algorithms
 * Easy (36.78%)
 * Likes:    1512
 * Dislikes: 159
 * Total Accepted:    399.8K
 * Total Submissions: 1.1M
 * Testcase Example:  '[3,2,0,-4]\n1'
 *
 * 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?
 * 
 */
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
// Use fast, slow pointers to determine whether there's a cycle in the linked list.
// Fast pointer moves 2 steps a time, slow pointer moves 1 step a time.
// If fast pointer catch up slow pointer, then there's a cycle in the linked list.
func hasCycle(head *ListNode) bool {
    if head == nil {
        return false
    }

    slow := head.Next
    if slow == nil {
        return false
    }

    fast := slow.Next

    for fast != nil && slow != nil {
        if fast == slow {
            return true
        }

        slow = slow.Next
        
        fast = fast.Next
        if fast != nil {
            fast = fast.Next
        }
    }

    return false
}