arcbjorn

thoughtbook

RSS Feed

Saturday, March 4, 2023

Linked list cycle II

Leetcode 142 problem.

Go

Slow & fast pointers

  • Time complexity: O(n)O(n) - n is a length of a list
  • Auxiliary space: O(1)O(1) - constant amount of space
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
    
    if head == nil || head.Next == nil {
        return nil
    }
    
    slow, fast := head, head
   
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        
        if fast == slow {
            
            slow = head
            
            for fast != slow {
                fast = fast.Next
                slow = slow.Next    
            }

            return slow
        }
    }
    
    return nil
}
Creative Commons Licence