Linked List Puzzles

A cycle in a linked list means some node's next pointer points back to a previously visited node, causing infinite traversal.

Floyd's cycle detection algorithm (tortoise and hare) uses two pointers: slow (one step) and fast (two steps). If they ever point to the same node, a cycle exists.

If fast reaches null or fast.next is null, the list is finite with no cycle.

This runs in O(n) time and O(1) space — far better than storing visited nodes in a Set (O(n) space).

function hasCycle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

Floyd's algorithm: The fast pointer gains one step on the slow pointer per iteration; if a cycle exists, it will inevitably lap the slow pointer.

To find where the cycle starts, reset one pointer to head after meeting and advance both at speed 1 — they meet at the cycle entry node.

Finding the middle without knowing the list length requires a two-pointer technique to avoid two full traversals.

The slow pointer advances one step at a time while the fast pointer advances two steps. When the fast pointer reaches the end, the slow pointer is at the middle.

For an even-length list, the slow pointer lands on the second of the two middle nodes — this is the convention in most problems (e.g., merge sort splitting).

This technique runs in O(n) time with a single pass and O(1) space.

function findMiddle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
}

Slow/fast pointer: The fast pointer moves twice as fast, so when it finishes the list, the slow pointer has covered exactly half the distance.

When used for splitting in merge sort, set fast = head.next to ensure slow stops at the first middle node for even-length lists.

Merging two sorted linked lists is similar to the merge step in merge sort — pick the smaller head from each list at every step.

Use a dummy node as the head of the result list. Compare the current nodes of both lists, attach the smaller one to the result, and advance that list's pointer.

When one list is exhausted, attach the remaining nodes of the other list directly (they are already sorted).

This runs in O(n + m) time and O(1) extra space since no new nodes are created — only pointers are rewired.

function mergeLists(l1, l2) {
  let dummy = {next: null}, curr = dummy;
  while (l1 && l2) {
    if (l1.val <= l2.val) { curr.next = l1; l1 = l1.next; }
    else { curr.next = l2; l2 = l2.next; }
    curr = curr.next;
  }
  curr.next = l1 || l2;
  return dummy.next;
}

Dummy head pattern: A dummy node eliminates special-casing for the first node insertion and keeps the loop logic uniform throughout.

The recursive version returns the smaller head and recursively merges the remaining — elegant but uses O(n) stack space for deeply nested calls.

Without knowing the list length, removing the nth node from the end requires either two passes or a two-pointer approach in one pass.

Use two pointers starting at a dummy node. Advance the first pointer n+1 steps ahead, then advance both until the first pointer reaches null — the second pointer is then just before the target node.

Using a dummy node before the head handles edge cases like removing the first node (n equals list length).

This runs in O(n) time with a single pass and O(1) extra space.

function removeNthFromEnd(head, n) {
  let dummy = {next: head}, first = dummy, second = dummy;
  for (let i = 0; i <= n; i++) first = first.next;
  while (first) { first = first.next; second = second.next; }
  second.next = second.next.next;
  return dummy.next;
}

Gap pointer technique: Keeping exactly n+1 steps between the two pointers ensures the trailing pointer lands at the node just before the target when the leader hits null.

The dummy node is essential for deleting the head node — without it you would need a separate if-branch to handle that case.

Two linked lists may share a common tail. The intersection point is the node where they merge into a single path.

Use two pointers, one starting at each head. When pointer A reaches null, redirect it to headB; when pointer B reaches null, redirect it to headA.

Both pointers now travel the same total distance (lenA + lenB), so they meet at the intersection node on the second pass — or both reach null if there is no intersection.

This runs in O(n + m) time and O(1) space with no need to know list lengths upfront.

function getIntersection(headA, headB) {
  let a = headA, b = headB;
  while (a !== b) {
    a = a ? a.next : headB;
    b = b ? b.next : headA;
  }
  return a;
}

Cross-traversal trick: By switching to the other list's head when reaching null, both pointers equalize their total path lengths and converge at the intersection.

If the lists do not intersect, both pointers become null simultaneously, and the loop exits — returning null correctly.

A linked list is a palindrome if it reads the same forwards and backwards — equivalent to comparing the first and second halves after reversing one.

Step 1: find the middle node using slow/fast pointers. Step 2: reverse the second half in-place. Step 3: compare the first and second halves node by node.

After comparison, restore the list by reversing the second half again if you need to preserve the original structure.

This runs in O(n) time and O(1) space — the key is reversing in-place rather than using an array or stack.

function isPalindrome(head) {
  let slow = head, fast = head, prev = null;
  while (fast && fast.next) {
    fast = fast.next.next;
    let next = slow.next;
    slow.next = prev; prev = slow; slow = next;
  }
  if (fast) slow = slow.next; // odd length
  while (prev && slow) {
    if (prev.val !== slow.val) return false;
    prev = prev.next; slow = slow.next;
  }
  return true;
}

Reverse second half in-place: This avoids using O(n) extra space from storing values in an array or stack.

For production code, always restore the list after checking — modifying the structure can cause bugs in code that holds references to specific nodes.

In a sorted linked list, duplicate values are adjacent, making it possible to detect and remove them in a single O(n) pass without extra memory.

Traverse the list with one pointer. Whenever the current node's value equals the next node's value, skip the next node by setting curr.next = curr.next.next.

If values differ, advance the pointer. Repeat until the end of the list.

This is O(n) time and O(1) space — no hash set needed because the sorted order guarantees all duplicates are consecutive.

function removeDuplicates(head) {
  let curr = head;
  while (curr && curr.next) {
    if (curr.val === curr.next.val) curr.next = curr.next.next;
    else curr = curr.next;
  }
  return head;
}

Don't advance on skip: When you skip a node, stay at curr and check curr.next again — there may be multiple consecutive duplicates to remove.

For unsorted lists, use a Set to track seen values; for sorted lists this single-pointer approach is always preferred.

When numbers are stored as linked lists with the least significant digit first, addition follows the same column-by-column process as manual arithmetic.

Traverse both lists simultaneously. At each position, sum the two digits (or 0 if one list is shorter) plus any carry from the previous position.

The new digit is sum % 10 and the new carry is Math.floor(sum / 10). Continue until both lists are exhausted and carry is 0.

The loop condition l1 || l2 || carry handles lists of different lengths and a final carry-over digit.

function addTwoNumbers(l1, l2) {
  let dummy = {next: null}, curr = dummy, carry = 0;
  while (l1 || l2 || carry) {
    let sum = (l1 ? l1.val : 0) + (l2 ? l2.val : 0) + carry;
    carry = Math.floor(sum / 10);
    curr.next = {val: sum % 10, next: null};
    curr = curr.next;
    if (l1) l1 = l1.next;
    if (l2) l2 = l2.next;
  }
  return dummy.next;
}

Include carry in loop condition: Even after both lists are exhausted, a remaining carry (e.g., 5+5=10) generates one more output node — do not exit early.

If digits are stored most-significant-first (reversed order), reverse both lists first, perform the addition, then reverse the result.

A multilevel doubly linked list has nodes with a child pointer that can lead to a separate sublist at a deeper level.

Use an iterative inline DFS: when you encounter a node with a child, splice the child sublist between the current node and its next sibling.

Steps: save curr.next, link curr.next = curr.child, set curr.child = null, find the tail of the child list, then connect that tail to the saved next.

This runs in O(n) time and O(1) extra space since no auxiliary stack is needed.

function flatten(head) {
  let curr = head;
  while (curr) {
    if (curr.child) {
      let next = curr.next, child = curr.child;
      curr.next = child; child.prev = curr; curr.child = null;
      let tail = child;
      while (tail.next) tail = tail.next;
      tail.next = next;
      if (next) next.prev = tail;
    }
    curr = curr.next;
  }
  return head;
}

Inline splicing: Inserting the child list directly avoids needing a separate stack and keeps the algorithm O(1) space.

After flattening, all child fields are null and the result is a standard doubly linked list — verify this in tests.

Each node has a next pointer and a random pointer which can point to any node or null, making direct copying non-trivial.

Use a HashMap: first pass creates a copy of every node stored in a map (original → copy), second pass assigns next and random on each copy using map lookups.

An O(1) space alternative interleaves copied nodes directly into the original list, sets random pointers, then separates the two lists back.

The HashMap approach is cleaner and runs in O(n) time and O(n) space.

function copyRandomList(head) {
  if (!head) return null;
  let map = new Map();
  let curr = head;
  while (curr) { map.set(curr, { val: curr.val, next: null, random: null }); curr = curr.next; }
  curr = head;
  while (curr) {
    if (curr.next) map.get(curr).next = map.get(curr.next);
    if (curr.random) map.get(curr).random = map.get(curr.random);
    curr = curr.next;
  }
  return map.get(head);
}

Two-pass HashMap: First pass clones all nodes; second pass wires next and random using map lookups in O(1) per node.

The interleaving O(1) space technique embeds copies between originals temporarily — it's trickier but eliminates the extra map allocation.

Merge sort is ideal for linked lists because it does not require random access and runs in O(n log n) time with O(log n) stack space.

Split the list into two halves using the slow/fast pointer technique, recursively sort each half, then merge the two sorted halves.

Quick sort is less suited for linked lists because pivot-based partitioning with pointers leads to worse cache performance.

Bottom-up merge sort achieves O(1) space by iterating with increasing merge sizes (1, 2, 4, ...) without recursion.

function sortList(head) {
  if (!head || !head.next) return head;
  let slow = head, fast = head.next;
  while (fast && fast.next) { slow = slow.next; fast = fast.next.next; }
  let mid = slow.next; slow.next = null;
  let left = sortList(head), right = sortList(mid);
  let dummy = {next: null}, curr = dummy;
  while (left && right) {
    if (left.val <= right.val) { curr.next = left; left = left.next; }
    else { curr.next = right; right = right.next; }
    curr = curr.next;
  }
  curr.next = left || right;
  return dummy.next;
}

Merge sort on lists: Split at the middle (slow/fast), sort recursively, and merge — all pointer operations, no array indexing needed.

For nearly sorted lists, insertion sort can outperform merge sort in practice due to lower constant overhead.

The reorder interleaves the beginning and end of the list, requiring three steps: find the middle, reverse the second half, then merge the two halves alternately.

Find the middle using slow/fast pointers, reverse the second half in place, then interleave nodes from the first and reversed second halves.

This runs in O(n) time and O(1) extra space — no additional arrays or data structures are needed.

Edge cases: single or two-node lists do not require reordering and should be returned as-is.

function reorderList(head) {
  if (!head || !head.next) return;
  let slow = head, fast = head;
  while (fast.next && fast.next.next) { slow = slow.next; fast = fast.next.next; }
  let prev = null, curr = slow.next; slow.next = null;
  while (curr) { let next = curr.next; curr.next = prev; prev = curr; curr = next; }
  let first = head, second = prev;
  while (second) {
    let n1 = first.next, n2 = second.next;
    first.next = second; second.next = n1;
    first = n1; second = n2;
  }
}

Three-step pattern: Find middle → reverse second half → interleave — each step is a classic linked list operation combined into one solution.

The merge step must stop when second is null; the first half may have one extra node for odd-length lists, which is handled automatically.

Reverse every k consecutive nodes as a group; if fewer than k nodes remain at the end, leave them as-is.

For each group, count k nodes, reverse those k nodes, then recursively process the remaining list and attach it to the group's tail.

The time complexity is O(n) and space complexity is O(n/k) due to recursion. An iterative approach achieves O(1) space.

Edge cases: if the list length is not divisible by k, the last partial group stays in its original order.

function reverseKGroup(head, k) {
  let curr = head, count = 0;
  while (curr && count < k) { curr = curr.next; count++; }
  if (count < k) return head;
  let prev = null; curr = head;
  for (let i = 0; i < k; i++) {
    let next = curr.next;
    curr.next = prev; prev = curr; curr = next;
  }
  head.next = reverseKGroup(curr, k);
  return prev;
}

Count before reversing: Always verify k nodes are available before reversing; do not modify the remaining partial group.

The iterative version uses extra pointers to track group start, end, and connection to the previous group — useful when stack depth is a concern.

Floyd's cycle detection finds whether a cycle exists, but finding the cycle start requires one more step.

Once slow and fast pointers meet inside the cycle, reset one pointer to the head. Move both one step at a time — they will meet at the cycle start.

Mathematical proof: the distance from head to cycle start equals the distance from the meeting point to cycle start when traveling forward — both pointers meet at the entry node.

This algorithm runs in O(n) time and O(1) space.

function detectCycleStart(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next; fast = fast.next.next;
    if (slow === fast) {
      slow = head;
      while (slow !== fast) { slow = slow.next; fast = fast.next; }
      return slow;
    }
  }
  return null;
}

Two-phase Floyd's: Phase 1 detects the cycle; phase 2 finds the entry point by resetting one pointer to head and advancing both at speed 1.

If the function returns null, the list has no cycle — always handle the no-cycle case before using the returned node.

Rotating right by k means the last k nodes move to the front; rotating left by k means the first k nodes move to the end.

First find the list length and normalize k (k = k % length). Then find the new tail at position (length - k - 1) from the head and the new head at position (length - k).

Connect the old tail to the old head to form a circle, then break the circle at the new tail to get the rotated list.

If k is 0 or equals the list length, no rotation is needed.

function rotateRight(head, k) {
  if (!head || !head.next || k === 0) return head;
  let tail = head, len = 1;
  while (tail.next) { tail = tail.next; len++; }
  k = k % len;
  if (k === 0) return head;
  tail.next = head; // make circular
  let newTail = head;
  for (let i = 0; i < len - k - 1; i++) newTail = newTail.next;
  let newHead = newTail.next;
  newTail.next = null;
  return newHead;
}

Circular trick: Temporarily connecting tail to head lets you traverse to the new break point without edge-case handling for wrapping.

Always normalize k with modulo before computing positions — without it, you may traverse far beyond the list length unnecessarily.

When you only have a reference to the node to delete (not the previous node or head), you cannot follow the standard approach of relinking the predecessor.

Instead, copy the value of the next node into the current node, then skip the next node by setting node.next = node.next.next.

This effectively deletes the node by replacing its value with its successor's value and removing the successor from the list.

This approach only works if the node is not the tail — the problem guarantees this constraint in most interview settings.

function deleteNode(node) {
  node.val = node.next.val;
  node.next = node.next.next;
}

Value copy trick: Since you cannot access the predecessor, copy the next node's value and unlink the next node — effectively "deleting" the current position.

This does not work on the last node; if called on a tail node, you would need access to the predecessor to properly remove it.

A sorted doubly linked list allows the two-pointer technique: one pointer starts at the head (smallest) and one at the tail (largest).

If the sum of both pointers equals the target, record the pair and move both inward. If the sum is less, move the left pointer right; if greater, move the right pointer left.

This runs in O(n) time and O(1) space, much better than the O(n²) brute force approach.

The doubly linked list's backward pointer makes it easy to traverse from the tail toward the head without reversing the list.

function findPairs(head, target) {
  let tail = head;
  while (tail.next) tail = tail.next;
  let result = [], left = head, right = tail;
  while (left !== right && left.prev !== right) {
    let sum = left.val + right.val;
    if (sum === target) { result.push([left.val, right.val]); left = left.next; right = right.prev; }
    else if (sum < target) left = left.next;
    else right = right.prev;
  }
  return result;
}

Two-pointer on doubly linked list: The bidirectional nature of DLL allows the same O(n) two-pointer technique used on sorted arrays.

The loop termination condition must account for lists with an even number of nodes (pointers pass each other) and odd (pointers meet at the same node).

Rearrange the list so all nodes with values less than x come before nodes with values greater than or equal to x, maintaining relative order.

Use two dummy-headed sublists: one for nodes less than x, one for nodes greater than or equal to x. Traverse the list once, appending each node to the appropriate sublist.

At the end, connect the tail of the less-than list to the head of the greater-or-equal list to form the partitioned result.

This is O(n) time and O(1) extra space (only 4 additional pointers are used).

function partition(head, x) {
  let lessHead = {next: null}, greaterHead = {next: null};
  let less = lessHead, greater = greaterHead;
  let curr = head;
  while (curr) {
    if (curr.val < x) { less.next = curr; less = less.next; }
    else { greater.next = curr; greater = greater.next; }
    curr = curr.next;
  }
  greater.next = null;
  less.next = greaterHead.next;
  return lessHead.next;
}

Dual sublist approach: Two dummy headers let you build both partitions simultaneously in a single pass, then join them — no extra memory beyond constant pointers.

Always set greater.next = null after the loop to avoid a cycle if the last node originally pointed to a node now in the less-than partition.

Swap every pair of adjacent nodes, not just their values — this is required when nodes are immutable by value but not by reference.

Use a dummy head to handle the edge case of the first pair. For each pair, rewire the three pointers: previous node's next, first node's next, and second node's next.

Recursively: swap the first two nodes, then recursively swap the rest and attach the result to the first node's next.

Both iterative and recursive approaches are O(n) time; the iterative approach uses O(1) space while recursion uses O(n/2) stack space.

function swapPairs(head) {
  let dummy = {next: head}, prev = dummy;
  while (prev.next && prev.next.next) {
    let a = prev.next, b = prev.next.next;
    prev.next = b;
    a.next = b.next;
    b.next = a;
    prev = a;
  }
  return dummy.next;
}

Dummy head pattern: Using a dummy node before the head eliminates special-casing for the first pair and keeps the loop uniform throughout the list.

After each swap, advance prev to the second node of the pair (which is now the trailing node) so it points to the start of the next pair.

First, use Floyd's cycle detection to find the meeting point of slow and fast pointers inside the cycle.

Once the meeting point is known, keep one pointer fixed and advance the other until it returns to the same node, counting the steps.

The count gives the exact length of the cycle in O(n) time and O(1) space.

If the list has no cycle, the function returns 0 — always check for cycle existence before measuring length.

function cycleLength(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next; fast = fast.next.next;
    if (slow === fast) {
      let count = 1, curr = slow.next;
      while (curr !== slow) { curr = curr.next; count++; }
      return count;
    }
  }
  return 0;
}

Post-detection counting: After Floyd's meeting point is found, traversing the cycle once from that point directly gives the cycle length in one additional O(cycle) pass.

Cycle length is useful for further operations such as finding the cycle start (set pointers cycle-length apart from head) or memory leak detection.

An in-order traversal of a BST visits nodes in sorted order, which maps naturally to a sorted doubly linked list.

During in-order traversal, maintain a prev pointer. For each visited node, set prev.right = curr and curr.left = prev (using left/right as prev/next pointers).

After the full traversal, connect the head and tail to make it circular, or leave them as null-terminated for a non-circular DLL.

This converts the BST in O(n) time in-place without any extra data structure.

function treeToDoublyList(root) {
  if (!root) return null;
  let head = null, prev = null;
  function inorder(node) {
    if (!node) return;
    inorder(node.left);
    if (prev) { prev.right = node; node.left = prev; }
    else head = node;
    prev = node;
    inorder(node.right);
  }
  inorder(root);
  head.left = prev; prev.right = head; // circular
  return head;
}

In-place in-order wiring: Reuse the tree's left and right pointers as DLL prev and next pointers — no new nodes or memory allocation needed.

Making the list circular (head.left = tail, tail.right = head) is a common interview follow-up — ensure both ends are connected.

A sorted doubly linked list can be searched for a pair with a given sum using two pointers — one at the start and one at the end — similar to the two-sum on a sorted array.

Move the left pointer right if the sum is too small, move the right pointer left if the sum is too large, and return true if an exact match is found.

This requires traversal to the tail first to get the right pointer, adding one O(n) pass before the O(n) search pass.

The overall complexity is O(n) time and O(1) space — no hash set or sorting needed.

function hasPairWithSum(head, target) {
  if (!head) return false;
  let left = head, right = head;
  while (right.next) right = right.next;
  while (left !== right && right.next !== left) {
    let sum = left.val + right.val;
    if (sum === target) return true;
    if (sum < target) left = left.next;
    else right = right.prev;
  }
  return false;
}

Two-pointer on DLL: The backward prev pointer eliminates the need to reverse the list or use extra memory compared to a singly linked list approach.

Always advance the pointers after a match if you want to find all pairs, not just detect existence — otherwise the loop becomes infinite at the match position.

Unlike a sorted list where duplicates are adjacent, an unsorted list requires tracking all seen values, typically with a hash set.

Traverse the list with a Set. For each node, if its value is already in the set, unlink it from the list. Otherwise, add it to the set and advance.

This runs in O(n) time and O(n) space for the hash set. If O(1) space is required, use a nested loop (runner pointer) at O(n²) time cost.

Always use a previous pointer to unlink nodes — you cannot unlink a node without a reference to the node before it.

function removeDuplicatesUnsorted(head) {
  let seen = new Set(), curr = head, prev = null;
  while (curr) {
    if (seen.has(curr.val)) {
      prev.next = curr.next;
    } else {
      seen.add(curr.val);
      prev = curr;
    }
    curr = curr.next;
  }
  return head;
}

Hash Set approach: O(n) time by storing all seen values — trade-off is O(n) space; justified when time performance is the priority.

The O(1) space "runner" technique uses a nested loop where the outer pointer fixes a node and the inner pointer removes all subsequent duplicates of that value.