5. How would you detect a cycle in a Linked List?

Basic

5. How would you detect a cycle in a Linked List?

Overview

Detecting a cycle in a Linked List is a common problem in computer science, essential for avoiding infinite loops in algorithms that traverse linked lists. It is crucial for ensuring the efficiency and reliability of software applications that utilize linked lists for data storage and manipulation.

Key Concepts

  1. Floyd’s Cycle-Finding Algorithm: Also known as the tortoise and the hare algorithm, it uses two pointers moving at different speeds to detect a cycle.
  2. Hashing: Keeping track of visited nodes to detect cycles by checking if a node is revisited.
  3. Two-Pointer Technique: Utilizes slow and fast pointers to identify cycles within a linked list efficiently.

Common Interview Questions

Basic Level

  1. How can you use Floyd’s Cycle-Finding Algorithm to detect a cycle in a linked list?
  2. Write a C# function to detect a cycle in a linked list using hashing.

Intermediate Level

  1. Can you improve cycle detection without using extra space?

Advanced Level

  1. How would you find the starting node of a cycle in a linked list?

Detailed Answers

1. How can you use Floyd’s Cycle-Finding Algorithm to detect a cycle in a linked list?

Answer: Floyd’s Cycle-Finding Algorithm, or the tortoise and the hare algorithm, involves two pointers moving through the list at different speeds (one advancing one step at a time, and the other two steps). If these pointers ever meet, a cycle exists in the list.

Key Points:
- Slow pointer advances one node at a time.
- Fast pointer advances two nodes at a time.
- If there is a cycle, the fast and slow pointers will eventually meet.

Example:

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int x) {
        val = x;
        next = null;
    }
}

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

2. Write a C# function to detect a cycle in a linked list using hashing.

Answer: Using hashing involves storing each visited node in a hash set. During traversal, if a node is encountered that is already in the hash set, a cycle is detected.

Key Points:
- Utilizes a hash set to keep track of visited nodes.
- Checks for repeated visits to the same node.
- Efficient for detecting cycles but requires extra space.

Example:

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int x) {
        val = x;
        next = null;
    }
}

public class Solution {
    public bool HasCycle(ListNode head) {
        HashSet<ListNode> nodesSeen = new HashSet<ListNode>();
        while (head != null) {
            if (nodesSeen.Contains(head)) {
                return true;
            }
            nodesSeen.Add(head);
            head = head.next;
        }
        return false;
    }
}

3. Can you improve cycle detection without using extra space?

Answer: Yes, improving cycle detection without extra space can be achieved by employing Floyd’s Cycle-Finding Algorithm, which only uses two pointers without additional data structures for storage.

Key Points:
- No extra space is used, making it space-efficient.
- Relies on the principle that if there is a cycle, two pointers moving at different speeds will eventually meet.
- Particularly useful for environments with limited memory availability.

Example: See the example provided in answer 1, as it already implements this approach.

4. How would you find the starting node of a cycle in a linked list?

Answer: To find the starting node of a cycle, you can use Floyd’s Cycle-Finding Algorithm to first detect the cycle. Once a cycle is detected, reset one pointer to the head of the list and move both pointers at the same pace. The point where they meet again is the start of the cycle.

Key Points:
- After detecting a cycle, use the meeting point to find the cycle’s start.
- Resetting one pointer to the head and moving both at the same pace from their positions.
- The meeting point of both pointers indicates the start of the cycle.

Example:

public class Solution {
    public ListNode DetectCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) { // Cycle detected
                ListNode slow2 = head;
                while (slow2 != slow) {
                    slow = slow.next;
                    slow2 = slow2.next;
                }
                return slow; // Start of the cycle
            }
        }
        return null; // No cycle
    }
}
logo