Start learning free

LESSON 314 OF 442 · LINKED LISTS

Linked List Cycle in Go: Slow and Fast Pointers in O(1) Space

Practice O(n) Read the full explanation

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. In the examples, pos is the index of the node that the tail's next pointer is connected to (-1 means no cycle). pos only describes how the example list is built: the tests build the cycle themselves, and pos is not passed to your function, which receives only head.

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

 

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed):
3 -> 2 -> 0 -> -4, and -4's next is the node 2 again.

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node:
1 -> 2, and 2's next is the node 1 again.

Example 3:

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

 

Constraints:

  • The number of the nodes in the list is in the range [0, 104].
  • -105 <= Node.val <= 105
  • pos is -1 or a valid index in the linked-list.

 

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

STEP 1 OF 7
    Ctrl + Enter to check

    GO · LINKED LISTS

    Linked List Cycle in Go, explained

    Problem overview

    hasCycle(head *ListNode) receives the first node of a singly linked list and reports whether the list contains a cycle: a node that can be reached again by following Next pointers. An empty list is nil. The list can have up to 10,000 nodes.

    For the list 3 -> 2 -> 0 -> -4 whose tail points back to the node holding 2, the answer is true. For 1 -> 2 where the tail points back to the head, it is true as well. For a single node with no link back, the answer is false. How the cycle was built is hidden from the function: it only sees the nodes.

    Approach: two pointers at different speeds

    Following Next pointers in a list without a cycle ends at nil. In a list with a cycle, it never does, so a plain walk would loop forever. A first fix is to remember every node already visited in a map and report a cycle when a node comes up twice. That works in O(n) time, but the map takes O(n) space, and the follow-up asks for constant memory.

    The constant-memory fix uses two pointers that move at different speeds. slow advances one node per step and fast advances two. Without a cycle, fast reaches the end and the walk stops. With a cycle, both pointers eventually enter it, and from then on fast gains exactly one node on slow per step. A gap that shrinks by one each step must reach zero, and then the pointers are on the same node. So the pointers meet if and only if there is a cycle.

    For 3 -> 2 -> 0 -> -4 with the tail linked to the node 2, the pointers move as follows, counting nodes from 0:

    Stepslow atfast at
    startnode 0 (3)node 0 (3)
    1node 1 (2)node 2 (0)
    2node 2 (0)node 1 (2)
    3node 3 (-4)node 3 (-4)

    After three steps both are on the same node, so the function returns true.

    Step by step

    1. Return false for fewer than two nodes. An empty list or a list whose first node has no Next can't have a cycle, unless that single node points to itself, which the guard doesn't catch because its Next isn't nil.
    2. Start both pointers at head with slow, fast := head, head.
    3. Loop while fast can move two nodes, which needs both fast and fast.Next to be non-nil.
    4. Move slow one node: slow = slow.Next.
    5. Move fast two nodes: fast = fast.Next.Next.
    6. Compare the pointers. If slow == fast, they are on the same node, so there is a cycle: return true.
    7. Return false after the loop. The loop only ends when fast has fallen off the end of the list, which can't happen in a cycle.

    The solution in Go

    func hasCycle(head *ListNode) bool {
	if head == nil || head.Next == nil {
		return false
	}
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast {
			return true
		}
	}
	return false
}

    The Go details worth a closer look:

    • Pointers compare by address. slow == fast asks whether the two pointers refer to the very same node, not whether the nodes hold equal values. A list such as 1 -> 1 -> 1 has equal values and no cycle, and it correctly returns false.
    • Short-circuit evaluation protects the dereference. In fast != nil && fast.Next != nil, the second test only runs when fast isn't nil. Reading fast.Next on a nil pointer would panic. The condition also guarantees that fast.Next.Next in the body is safe, since fast.Next is known not to be nil.
    • Multiple assignment. slow, fast := head, head declares both variables in one line. Both are *ListNode, the type of head.
    • Only for. Go has no while. A for with just a condition is its while loop.
    • The type is the lesson's. The code uses a struct ListNode with Val int and Next *ListNode. A program that runs this function outside the lesson needs that declaration.

    Complexity

    Time: O(n). Without a cycle, fast reaches the end after about n / 2 steps. With a cycle, slow enters it within n steps, and the pointers then meet within one more lap of the cycle, which is at most another n steps. Every step is constant work.

    Space: O(1). Two pointers, no matter the length of the list.

    Edge cases and common mistakes

    • Empty list. head is nil, and the guard returns false before any dereference.
    • One node, no cycle. head.Next is nil, so the answer is false.
    • One node pointing to itself. The guard passes. The first step leaves both pointers on that node, and the function returns true.
    • Two nodes forming a loop. 1 -> 2 -> 1 returns true: after one step slow is on the second node and fast is back on the first, and after the second step both are on the first node.
    • Comparing values instead of pointers. Equal values don't prove a cycle. Compare the pointers.
    • Checking the meeting point before moving. Both pointers start on the same node, so a comparison before the first move would always report a cycle. The comparison belongs after the moves.
    • Testing only fast.Next in the loop condition. When the list has an even length, fast becomes nil. The condition has to test fast itself first.

    Testing

    • Values [3, 2, 0, -4] with the tail linked to index 1 gives true.
    • Values [1, 2] with the tail linked to index 0 gives true.
    • Values [1] with no link back gives false.
    • Values [1, 2, 3] with no link back gives false.
    • An empty list gives false.
    Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free