Linked List Cycle

Easy

Asked by:

+11

More companies

104 views

Topics:

Linked ListsTwo Pointers

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. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

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).

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.

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, 10⁴].
-10⁵ <= Node.val <= 10⁵
pos is -1 or a valid index in the linked-list.

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What should I return if the input `head` is null, representing an empty list?
Can the linked list contain duplicate node values, and does that affect the definition of a cycle?
Is it possible for the list to be very large, for example, containing millions of nodes?
Is the `next` pointer of the last node in a non-cyclic list guaranteed to be null?
Are there any constraints on the values stored within the nodes themselves, such as their range or data type?

Brute Force Solution

Approach

The brute force strategy is like leaving a breadcrumb on every stone you step on as you walk down a path. If you ever come across a stone that already has a breadcrumb, you know you've been walking in a circle.

Here's how the algorithm would work step-by-step:

Imagine you have a list of all the items you've visited so far. To begin, this list is empty.
Start at the very first item in the linked list.
Check your list of visited items. Have you seen this specific item before?
If you have seen it before, then you've found a cycle, and you are done.
If you haven't seen it before, add it to your list of visited items so you'll remember it for later.
Then, move to the very next item in the linked list.
Repeat this process: check if you've seen the new item before, and if not, add it to your visited list and move on.
If you reach the end of the path without ever seeing the same item twice, it means there is no circle.

Code Implementation

class ListNode:
    def __init__(self, value=0, next_node=None):
        self.val = value
        self.next = next_node

def hasCycle(head_node):
    # This set will act as our notebook to keep a record of every single item we have visited.
    visited_nodes = set()
    current_node = head_node

    while current_node is not None:
        # Before proceeding, we check our notebook to see if we've already visited this exact item.
        if current_node in visited_nodes:

            # If the current item is already in our notebook, it means we have a cycle.
            return True

        # If we haven't seen this item before, we add it to our notebook for future reference.
        visited_nodes.add(current_node)
        current_node = current_node.next

    return False

Big(O) Analysis

Time Complexity

O(n) – To determine if a cycle exists, we must traverse the linked list, examining each node one by one. Let n be the number of nodes in the list. For every node we visit, we perform a lookup in our set of previously seen nodes, which takes constant time on average, and then add the current node to the set, also a constant time operation. In the worst-case scenario, where there is no cycle, we visit all n nodes, resulting in a total of n lookup and n insertion operations. This leads to a linear number of operations proportional to n, which simplifies to O(n).

Space Complexity

O(N) – The space complexity is determined by the auxiliary list used to keep track of visited items, as described in the explanation. In the worst-case scenario of a linked list with no cycle, we would traverse all N nodes and add each one to our visited list. Therefore, the extra space required grows linearly with the number of nodes, N, in the linked list.

Optimal Solution

Approach

The clever solution is to imagine two pointers moving through the list, but at different speeds. By observing how these two pointers interact, we can determine if they will ever meet again, which would only happen if the path they are on is a circle.

Here's how the algorithm would work step-by-step:

Imagine you have two pointers, one slow and one fast, both starting at the very beginning of the list.
On each turn, move the slow pointer one step forward.
At the same time, move the fast pointer two steps forward.
If the list has a cycle, the fast pointer will eventually lap the slow pointer, and they will land on the exact same spot.
Think of it like two runners on a circular track; the faster runner will always eventually overtake the slower one.
If the fast pointer reaches the end of the list, it means there was no cycle, because it never had a chance to lap the slow one.
So, if they ever meet, there's a cycle. If the fast one finishes, there isn't.

Code Implementation

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def hasCycle(head):
    # The fast runner will reach the end first if there is no cycle.
    if not head or not head.next:
        return False

    slow_walker = head
    fast_runner = head

    while fast_runner and fast_runner.next:
        slow_walker = slow_walker.next
        fast_runner = fast_runner.next.next

        # If the pointers meet, the fast runner has lapped the slow one, proving a cycle exists.
        if slow_walker == fast_runner:
            return True

    # If the loop finishes, the fast runner reached the end, so there is no cycle.
    return False

Big(O) Analysis

Time Complexity

O(n) – The time complexity is determined by the movement of the two pointers, slow and fast, through the linked list of n nodes. In the worst-case scenario (no cycle), the fast pointer traverses the entire list, visiting each node once. In the case of a cycle, the fast pointer enters the cycle and will meet the slow pointer within a number of steps proportional to the length of the cycle and the non-cyclic part. Because the number of steps taken by the pointers is directly proportional to the number of nodes, n, the total operations scale linearly with the size of the list, resulting in a time complexity of O(n).

Space Complexity

O(1) – The algorithm uses a fixed number of variables, specifically two pointers (slow and fast), to traverse the linked list. The amount of extra memory required for these pointers does not change, regardless of the number of nodes (N) in the list. Since the memory usage is constant and independent of the input size, the space complexity is O(1).

Edge Cases

Case	How to Handle
Null head pointer (empty list)	The initial check for head being null or head.next being null correctly returns false as a cycle requires at least one node pointing to itself or another.
Linked list with only one node	A single node can either point to null (no cycle) or to itself (cycle), both of which are handled correctly by the two-pointer approach.
Linked list with two nodes	The two-pointer algorithm correctly detects both the no-cycle case (A->B->null) and the cycle case (A->B->A).
Cycle starts at the head of the list	The slow and fast pointers will eventually meet within the cycle, regardless of where the cycle begins.
A 'lollipop' structure where the cycle begins after a long non-cyclic path	The fast pointer is guaranteed to enter the cycle first and will eventually be lapped by the slow pointer within the cycle portion.
The entire list is one large cycle	The fast pointer will lap the slow pointer, and they will meet, correctly identifying the cycle.
A very long linked list (maximum size)	The two-pointer solution uses constant O(1) extra space, making it highly efficient and scalable for very large lists without memory issues.
A single node pointing to itself (self-loop)	The fast pointer will advance and immediately meet the slow pointer at the head, correctly identifying the cycle.

Null head pointer (empty list)

How to Handle:

The initial check for head being null or head.next being null correctly returns false as a cycle requires at least one node pointing to itself or another.

Linked list with only one node

How to Handle:

A single node can either point to null (no cycle) or to itself (cycle), both of which are handled correctly by the two-pointer approach.

Linked list with two nodes

How to Handle:

The two-pointer algorithm correctly detects both the no-cycle case (A->B->null) and the cycle case (A->B->A).

Cycle starts at the head of the list

How to Handle:

The slow and fast pointers will eventually meet within the cycle, regardless of where the cycle begins.

A 'lollipop' structure where the cycle begins after a long non-cyclic path

How to Handle:

The fast pointer is guaranteed to enter the cycle first and will eventually be lapped by the slow pointer within the cycle portion.

The entire list is one large cycle

How to Handle:

The fast pointer will lap the slow pointer, and they will meet, correctly identifying the cycle.

A very long linked list (maximum size)

How to Handle:

The two-pointer solution uses constant O(1) extra space, making it highly efficient and scalable for very large lists without memory issues.

A single node pointing to itself (self-loop)

How to Handle:

The fast pointer will advance and immediately meet the slow pointer at the head, correctly identifying the cycle.