Two Pointers on linked list

Question

Given a singly linked list, implement the two pointers technique to detect if there is a cycle in the list. Return true if a cycle exists and false otherwise. You should aim for O(n) time complexity and O(1) space complexity.

Codemia · Accepted Answer

To determine if a linked list has a cycle, we can effectively utilize the **Two Pointers** technique, specifically the **Floyd’s Cycle Detection Algorithm**. This approach involves two pointers that traverse the linked list at different speeds. The fast pointer moves two steps at a time, while the slow pointer moves one step at a time. If there is a cycle, the fast pointer will eventually meet the slow pointer. The reason this method is suitable is that it allows us to detect cycles in O(n) time without using extra space for a hash map or a set, thus achieving O(1) space complexity.

1. Initialize two pointers: `slow` and `fast`. Both start at the head of the linked list.
2. Move `slow` one step forward and `fast` two steps forward in each iteration.
3. If `fast` reaches the end of the list (`None`), return `False`, as there is no cycle.
4. If `slow` meets `fast`, return `True`, indicating a cycle exists.
5. Continue this until either a cycle is found or the end of the list is reached.

**Example:** For the linked list `1 -> 2 -> 3 -> 4 -> 5`, if there is a cycle back to `3`, the pointers would meet at node `3`. If there is no cycle, `fast` will reach `None` after traversing the list.

Here is the implementation of the algorithm in Python:

```python
class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

def hasCycle(head: ListNode) -> bool:
    if not head or not head.next:
        return False

slow = head
    fast = head

while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True

return False
```

The time complexity of this solution is **O(n)** because in the worst case, both pointers will traverse the entire linked list once. The space complexity is **O(1)** since we are only using a constant amount of space for the two pointers, regardless of the size of the linked list.

1. **Empty List**: If the head is `None`, there are no nodes to form a cycle, so the output should be `False`.
2. **Single Node**: If there is a single node that points to itself (cycle), the function should return `True`. If it points to `None`, it should return `False`.
3. **Large List without Cycle**: A long linked list that does not contain any cycles should return `False`.
4. **List with Multiple Nodes and a Cycle**: Ensure the function correctly identifies cycles in various placements (e.g., beginning, middle, end of the list).

Two Pointers on linked list

Rippling

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Rippling Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string