Linked Lists Explained

A linked list is a linear collection of nodes where each node stores a value and a pointer to the next node. Unlike arrays, insertion and deletion at any known position cost O(1), but random access is O(n) because you must walk from the head. Linked list problems appear at every FAANG company, usually testing pointer manipulation and edge cases.

Singly vs Doubly Linked Lists

• Singly: each node has a next pointer only. Traversal is one-way.
• Doubly: each node has prev and next. Deletion of a node given a pointer is easier, but every node costs one extra pointer.

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

The Reverse Pattern

Reversing a linked list in place is the single most asked linked list problem. Memorize the three-pointer loop:

function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let curr = head;
  while (curr) {
    const next = curr.next;   // save next before rewiring
    curr.next = prev;          // flip the pointer
    prev = curr;               // advance prev
    curr = next;               // advance curr
  }
  return prev;                 // prev is the new head
}
// Time: O(n), Space: O(1)

The Dummy Node Pattern

A dummy node sits before the head so the real head can change without special-casing. Return dummy.next, which is the true head after the operation.

function removeElements(head: ListNode | null, val: number): ListNode | null {
  const dummy = new ListNode(0, head);
  let curr = dummy;
  while (curr.next) {
    if (curr.next.val === val) curr.next = curr.next.next;
    else curr = curr.next;
  }
  return dummy.next;
}

The Fast and Slow Pointer Pattern

Two pointers, one moving twice as fast, solve cycle detection and middle-of-list problems in O(1) space. Floyd's cycle detection uses the same idea : if the fast pointer ever catches the slow pointer, there is a cycle.

function hasCycle(head: ListNode | null): boolean {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow!.next ?? null;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

Finding the Middle Node

Advance slow by one and fast by two. When fast reaches the end, slow is at the middle. This is the standard split step for merge sort on a linked list.

Two-Pointer Techniques

• Reverse in groups: reverse K nodes at a time, stitching each group back.
• Merging two sorted lists: walk both lists with a dummy tail, always attach the smaller node.
• Intersection detection: align both lists by length, then walk together looking for the shared node.
• Partition around a value: build two lists (less and greater) with dummy heads, then concatenate.

Common Mistakes

• Losing the pointer to next before rewiring : always store it first.
• Forgetting that head may be null or may change, so a dummy node is safer.
• Returning the old head after a reorder : after reversing or rotating, the head changes.
• Null dereference on fast.next in cycle detection : check both before advancing.
• Creating cycles accidentally when reversing with improper termination.

Frequently Asked Questions

Related Tutorials

• Two Pointers : fast-slow and alignment patterns half the work.
• Stack and Queue : convert list traversal order to stack behavior for reversing visits.
• Arrays and Strings : when to reach for an array instead.
• Linked list practice problems : company-tagged problems.