Coding Interview Questions | Linked List Cycle

December 23rd, 2023

Introduction:

This summary will talk about my solution to the linked list cycle problem as seen on leetcode here.

Solution:

function hasCycle(head: ListNode | null): boolean {
  let currPtr = head;
  let nextPtr = head?.next ?? null;

  while (currPtr !== null && nextPtr !== null) {
    if (currPtr === nextPtr) {
      return true;
    }

    if (currPtr.next) {
      currPtr = currPtr.next;
    }

    if (nextPtr.next?.next) {
      nextPtr = nextPtr.next.next;
    } else {
      nextPtr = null;
    }
  }

  return false;
}

Summary:

1. Initialization: Two pointers, currPtr and nextPtr, are initialized to the head of the linked list. nextPtr is set to the next node if it exists, otherwise, it is set to null.

2. Main Loop: A while loop is used to traverse the linked list. The loop continues as long as both pointers (currPtr and nextPtr) are not null.

3. Cycle Detection: Inside the loop, it checks if currPtr is equal to nextPtr, which would indicate the presence of a cycle. If true, the function returns true, indicating the existence of a cycle.

4. Pointer Movements: The pointers are then moved based on the following conditions:

   • currPtr moves one step (currPtr = currPtr.next) if it has a next node.
   • nextPtr moves two steps (nextPtr = nextPtr.next.next) if it has at least two next nodes. Otherwise, it is set to null.

5. Loop Termination: The loop continues until either of the pointers becomes null, signifying the end of the linked list.

6. Cycle Absence: If the loop completes without detecting a cycle, the function returns false, indicating that no cycle is present in the linked list.

The solution uses the Floyd’s Tortoise and Hare algorithm to detect cycles in a linked list. The two pointers move at different speeds, and if there is a cycle, they are guaranteed to meet at some point. The null checks and termination conditions ensure the correctness of the algorithm.

Bonus Solution:

Here is a more elegant solution that incorporates some better variable names and reduces the amount of redunant if checks seen in my original solution.

function hasCycle(head: ListNode | null): boolean {
  let slow = head;
  let fast = head;

  while (fast !== null && fast.next !== null) {
    slow = slow!.next;
    fast = fast.next.next;

    if (slow === fast) {
      return true;
    }
  }

  return false;
}