Start learning free

LESSON 313 OF 441 · LINKED LISTS

Linked List Cycle in C#: Floyd's Two 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 9
    Ctrl + Enter to check

    C# · LINKED LISTS

    Linked List Cycle in C#, explained

    Problem overview

    The method HasCycle receives the head of a singly linked list of ListNode objects and returns a bool: true if following the next pointers can bring you back to a node you already visited, false if the chain ends in null.

    The statement mentions pos, the index of the node the tail links back to. It only describes how the test list was built. The method never receives it, so it has to find the cycle from the nodes alone.

    Take [3, 2, 0, -4] where the last node points back to the node holding 2. Walking from the head gives 3, 2, 0, -4, 2, 0, -4, 2, and so on forever, so the answer is true. For [1] with no link back, the walk ends at once and the answer is false. The list can also be empty (head is null), which has no cycle.

    Approach: a slow and a fast pointer

    The obvious solution keeps a HashSet<ListNode> of the nodes seen so far and returns true when a node shows up twice. It is correct, but it uses O(n) extra memory. The follow-up asks for constant memory.

    The constant-memory idea is Floyd's cycle detection, nicknamed the tortoise and the hare. Keep two references that start at the head. In every round, the slow one moves one node and the fast one moves two. Then:

    • If there is no cycle, the fast pointer runs off the end of the list and the loop stops.
    • If there is a cycle, both pointers end up inside it. Inside a loop, the fast pointer gains exactly one node per round on the slow one, so the gap between them shrinks by one each round until it is zero, and the two references point at the same node.

    The gap can't jump over zero, because it changes by one at a time. That is why moving by 1 and 2 is the right pair of speeds: the pointers cannot pass each other without landing on the same node first.

    On [3, 2, 0, -4] with the tail linked to the node holding 2, the pointers move like this:

    RoundSlowFast
    start33
    120
    202
    3-4-4

    After round 3 both are on the node holding -4, so a cycle exists.

    Step by step

    1. Create two references, temp (slow) and temp1 (fast), both starting at head.
    2. Guard the short lists. If head is null or head.next is null, the list has zero or one node with nothing after it, so it can't loop. The || operator stops at the first true operand, so head.next is never read when head is null.
    3. Return false inside the guard.
    4. Loop while the fast pointer can move two nodes. That needs both temp1 and temp1.next to be non-null. Checking temp1 first with && protects the second check.
    5. Move the fast pointer with temp1 = temp1.next.next.
    6. Move the slow pointer with temp = temp.next.
    7. Compare the pointers after moving them. Both start on head, so comparing before the first move would report a cycle for every list.
    8. Return true when they are the same node.
    9. Return false after the loop. The loop only ends when the fast pointer reached the end of the list.

    The solution in C#

    class Solution {
    public bool HasCycle(ListNode head) {
        ListNode temp = head;
        ListNode temp1 = head;
        if(head == null || head.next == null){
            return false;
        }
        while (temp1 != null && temp1.next != null){
            temp1 = temp1.next.next;
            temp = temp.next;
            if(temp == temp1){
                return true;
            }
        }
        return false;
    }
}

    The C# details worth knowing:

    • ListNode is a class, so == compares references. temp == temp1 is true only when both variables point at the very same object. A list [1, 1, 1, 1] without a cycle returns false, because four different nodes that hold equal values are still four different objects. Comparing temp.val == temp1.val instead would be a bug.
    • Chained member access. temp1.next.next throws a NullReferenceException if temp1.next is null. The loop condition exists to make sure that never happens.
    • Short-circuit operators. In temp1 != null && temp1.next != null, the right side runs only when the left side is true. Swapping the two operands would crash on a null fast pointer.
    • Self-loop. A single node whose next is itself passes the guard, because head.next is not null. In the loop both pointers land on that node, so the method returns true.

    Complexity

    Time: O(n). Without a cycle, the fast pointer reaches the end after about n / 2 rounds. With a cycle, the slow pointer enters the cycle after at most n steps, and once both pointers are inside, the fast one closes the gap within one lap of the cycle. The total number of rounds stays proportional to the number of nodes.

    Space: O(1). The method keeps two references and nothing else, whatever the length of the list. This is the improvement over a hash set of visited nodes.

    Edge cases and common mistakes

    • Empty list. head == null returns false. The loop condition would also handle it, so the guard is a clear early exit rather than a necessity.
    • One node, no cycle. Returns false. One node pointing at itself returns true.
    • Two nodes forming a loop. [1, 2] with the tail linked to the head returns true: after round 1 the slow pointer is on the second node and the fast pointer on the head, and after round 2 both are on the second node.
    • The tail links to the head. [1, 2, 3, 4, 5] with the last node pointing at the first one returns true, as does a tail that links to itself.
    • Comparing values instead of nodes. Duplicate values are normal in a list, and they say nothing about a cycle.
    • Checking equality before moving. Both pointers begin on the same node, so the comparison has to come after the moves.
    • Only checking temp1.next. When the list has an even number of nodes, temp1 itself becomes null after a jump, so the loop condition has to test it too.

    Testing

    • [3, 2, 0, -4] with the tail linked to index 1 gives true.
    • [1, 2] with the tail linked to index 0 gives true.
    • [1] with no link gives false.
    • [1, 1, 1, 1] with no link gives false.
    • [1, 2, 3, 4, 5] with the tail linked to index 4 (itself) gives true.
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free