Linked Lists and Pointer Techniques

A linked list stores nodes where each node points to the next node. Unlike arrays, insertion at head is O(1) and memory is non-contiguous.

Singly linked list essentials

A linked list stores nodes where each node points to the next node. Unlike arrays, insertion at head is O(1) and memory is non-contiguous.

Traversal: O(n)
Insert/Delete at head: O(1)
Search by value: O(n)

Fast and slow pointer

Detect cycle in linked list

type Node = { value: number; next: Node | null };

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

  while (fast && fast.next) {
    slow = slow?.next ?? null;
    fast = fast.next.next;
    if (slow && fast && slow === fast) return true;
  }

  return false;
}