Linked list

A linked list is a data structure consisting of nodes, where each node contains a value and a reference (pointer) to the next node. Unlike arrays, linked lists do not store elements contiguously in memory. This makes insertion and deletion operations more flexible but requires careful pointer management.

Key points to keep in mind:

• The head points to the first element, and losing it can result in losing access to the entire list
• Traversal requires following next pointers until null is reached
• Linked lists can easily form cycles, which must be handled to avoid infinite loops
• Operations that are trivial in arrays, like accessing the i-th element, require O(n) traversal in linked lists

Understanding these fundamentals is crucial before diving into more advanced linked list patterns such as two pointers, reversals, and cycle detection.

Operations

Before tackling advanced patterns, it’s important to master the basic operations on a linked list. All the snippets below are based on a ListNode data structure with the following definition.

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val: number) {
    this.val = val;
    this.next = null;
  }
}

When working with linked lists, edge cases often arise when inserting or deleting nodes at the head of the list. To handle these cases cleanly, we introduce a dummy node: a temporary node placed before the head. This allows all operations to be implemented uniformly, without special checks for the head.

For traversing a linked list, you typically start from the head and follow the next pointers until you reach the end (null).

function traverse(head: ListNode | null): void {
    const dummy = new ListNode(0);
    dummy.next = head;

    let curr: ListNode | null = dummy.next;

    while (curr) {
        console.log(curr.val);
        curr = curr.next;
    }
};

The same technique can be applied to other operations like insertion and deletion, making the code cleaner and easier to manage. For example to insert a new node at a given position:

function insertAtPosition(head: ListNode | null, val: number, pos: number): ListNode | null {
  const dummy = new ListNode(0);
  dummy.next = head;
  
  let prev: ListNode | null = dummy;
  let index = 0;

  while (prev && index < pos) {
    prev = prev.next;
    index++;
  }

  if (prev) {
    const newNode = new ListNode(val);
    newNode.next = prev.next;
    prev.next = newNode;
  }

  return dummy.next;
}

The same dummy node approach can be used for deletion by adjusting the next pointers to skip over the target node:

function deleteByValue(head: ListNode | null, target: number): ListNode | null {
  const dummy = new ListNode(0);
  dummy.next = head;

  let prev: ListNode | null = dummy;
  let curr: ListNode | null = dummy.next;

  while (curr) {
    if (curr.val === target) {
      prev!.next = curr.next;
      break;
    }

    prev = curr;
    curr = curr.next;
  }

  return dummy.next;
}

Reversal Techniques

Reversing a linked list (fully or partially) is one of the most important skills when working with linked lists. A lot of problems require reversing the entire list or a portion of it.

The algorithm to reverse a linked list involves three main steps:

• Iterate through the list
• Reverse the next pointer of each node
• Move forward while keeping track of the previous node

function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let curr: ListNode | null = head;

  while (curr !== null) {
    const nextTemp = curr.next;
    curr.next = prev;
    prev = curr;
    curr = nextTemp;
  }

  return prev;
}

For partial reversal, such as reversing a sublist from position m to n, we can use a similar approach but with additional pointers to manage the boundaries of the sublist.

function reverseBetween(
  head: ListNode | null,
  m: number,
  n: number
): ListNode | null {
  const dummy = new ListNode(0);
  dummy.next = head;

  let prev: ListNode | null = dummy;

  for (let i = 1; i < m; i++) {
    prev = prev!.next;
  }

  let start = prev!.next; // first node of the sublist
  let then = start!.next; // node to be repositioned

  for (let i = 0; i < n - m; i++) {
    start!.next = then!.next;
    then!.next = prev!.next;
    prev!.next = then;
    then = start!.next;
  }

  return dummy.next;
}

Detecting Cycles (Floyd’s Cycle Finding Algorithm)

Cycle detection is a classic linked list problem: given a list, determine whether a node eventually points back to a previous one. The most common and efficient solution is Floyd’s Cycle Finding Algorithm, also known as the Tortoise and Hare approach.

Use two pointers:

• slow moves one step at a time
• fast moves two steps at a time
• if a cycle exists, the two pointers will eventually meet
• if fast reaches the end, the list has no cycle

Once a cycle is detected, it is possible to find the starting node of the cycle by:

• reset one pointer to the head
• move both pointers one step at a time
• the point where they meet again is the start of the cycle

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;
}

Time & Space Complexity

Linked lists trade constant-time pointer manipulation for linear-time traversal. Understanding where each cost comes from is essential to choosing the right data structure and technique.

Exercises