Common Linked List Problems

Linked lists are one of the most tested data structures in coding interviews. Unlike arrays, they offer O(1) insertions and deletions at known positions, but sacrifice random access. Most linked-list problems share a small bag of tricks: slow/fast pointers, dummy nodes, in-place reversal, and two-pass length counting. Master these patterns and you can solve almost any linked-list problem you encounter.

All examples use this minimal node definition:

class ListNode {
  constructor(val = 0, next = null) {
    this.val = val;
    this.next = next;
  }
}

// Helper: build a list from an array
function buildList(arr) {
  const dummy = new ListNode(0);
  let cur = dummy;
  for (const v of arr) {
    cur.next = new ListNode(v);
    cur = cur.next;
  }
  return dummy.next;
}

// Helper: collect a list into an array (for testing)
function toArray(head) {
  const result = [];
  while (head) {
    result.push(head.val);
    head = head.next;
  }
  return result;
}

1. Reverse a Linked List

Problem: Given the head of a singly linked list, reverse it and return the new head.

Key insight: Walk the list once, redirecting each node's next pointer backward. You need three pointers — prev, curr, and next — to avoid losing your place.

Step-by-step diagram

Starting list: 1 → 2 → 3 → 4 → null

Step 0: prev=null  curr=1  next=2
        null  ←  1    2 → 3 → 4

Step 1: prev=1    curr=2  next=3
        null ← 1 ← 2    3 → 4

Step 2: prev=2    curr=3  next=4
        null ← 1 ← 2 ← 3    4

Step 3: prev=3    curr=4  next=null
        null ← 1 ← 2 ← 3 ← 4

Return prev (= 4), the new head.

Iterative solution

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

  while (curr !== null) {
    const next = curr.next; // save the rest of the list
    curr.next = prev;       // flip the pointer
    prev = curr;            // advance prev
    curr = next;            // advance curr
  }

  return prev; // prev is the new head
}

// Test
const list = buildList([1, 2, 3, 4, 5]);
console.log(toArray(reverseList(list))); // [5, 4, 3, 2, 1]

Recursive solution

The recursive approach is elegant but uses O(n) stack space. It trusts the recursion to reach the tail, then wires pointers on the way back up.

function reverseListRecursive(head) {
  // Base case: empty list or single node
  if (head === null || head.next === null) return head;

  // Recurse: reverse everything after head
  const newHead = reverseListRecursive(head.next);

  // On the way back: make head.next point back to head
  head.next.next = head;
  head.next = null;

  return newHead;
}

	Time	Space
Iterative	O(n)	O(1)
Recursive	O(n)	O(n) call stack

2. Detect a Cycle (Floyd's Algorithm)

Problem: Given a linked list, return true if it contains a cycle.

Key insight — Floyd's Tortoise and Hare: Use two pointers: slow advances one step at a time, fast advances two. If a cycle exists, fast laps slow inside the cycle and they meet. If there is no cycle, fast reaches null.

Why does it work? Imagine the cycle has length C and the tail is k nodes from the entry point. Once both pointers are inside the cycle, the gap between them shrinks by 1 on each iteration (fast gains one step per round). They are guaranteed to meet after at most C iterations.

function hasCycle(head) {
  let slow = head;
  let fast = head;

  while (fast !== null && fast.next !== null) {
    slow = slow.next;       // 1 step
    fast = fast.next.next;  // 2 steps

    if (slow === fast) return true; // they met — cycle detected
  }

  return false; // fast hit null — no cycle
}

// Build a list with a cycle for testing
const n1 = new ListNode(3);
const n2 = new ListNode(2);
const n3 = new ListNode(0);
const n4 = new ListNode(-4);
n1.next = n2; n2.next = n3; n3.next = n4; n4.next = n2; // cycle back to n2
console.log(hasCycle(n1)); // true

Note

Floyd's algorithm can also find the cycle entry point. After slow and fast meet, reset one pointer to head and advance both one step at a time. They will meet exactly at the cycle's entrance.

	Time	Space
Floyd's algorithm	O(n)	O(1)

3. Find the Middle Node

Problem: Return the middle node of a linked list. For even-length lists, return the second middle node.

Key insight: The slow/fast pointer trick again. When fast reaches the end, slow is exactly at the middle. For a list of length n, fast takes ⌊n/2⌋ full steps, so slow lands on node ⌊n/2⌋.

function middleNode(head) {
  let slow = head;
  let fast = head;

  // fast moves 2 steps; slow moves 1
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
  }

  return slow; // slow is the middle
}

// Odd length: [1,2,3,4,5] → middle = 3
console.log(middleNode(buildList([1, 2, 3, 4, 5])).val); // 3

// Even length: [1,2,3,4] → second middle = 3
console.log(middleNode(buildList([1, 2, 3, 4])).val); // 3

	Time	Space
Slow/fast pointer	O(n)	O(1)

4. Merge Two Sorted Lists

Problem: Merge two sorted linked lists and return the sorted merged list.

Key insight: Use a dummy node as the anchor for the result list. Compare the heads of both lists, attach the smaller node to the result, and advance that list's pointer. When one list is exhausted, attach the remainder of the other.

function mergeTwoLists(list1, list2) {
  const dummy = new ListNode(0); // anchor — never moved
  let cur = dummy;

  while (list1 !== null && list2 !== null) {
    if (list1.val <= list2.val) {
      cur.next = list1;
      list1 = list1.next;
    } else {
      cur.next = list2;
      list2 = list2.next;
    }
    cur = cur.next;
  }

  // Attach the remaining nodes (at most one list is non-null)
  cur.next = list1 !== null ? list1 : list2;

  return dummy.next;
}

const a = buildList([1, 2, 4]);
const b = buildList([1, 3, 4]);
console.log(toArray(mergeTwoLists(a, b))); // [1, 1, 2, 3, 4, 4]

Tip

The dummy node pattern eliminates the "is this the first node?" special case. You never have to update the head pointer inside the loop — just return dummy.next at the end.

	Time	Space
Iterative merge	O(m + n)	O(1)

5. Remove Nth Node From End

Problem: Remove the nth node from the end of a linked list in one pass.

Key insight: Create a gap of exactly n nodes between a fast and a slow pointer. When fast reaches the last node, slow is right before the node to delete. A dummy node handles edge cases like removing the head.

function removeNthFromEnd(head, n) {
  const dummy = new ListNode(0, head);
  let fast = dummy;
  let slow = dummy;

  // Advance fast by n+1 steps to create an n-node gap
  for (let i = 0; i <= n; i++) {
    fast = fast.next;
  }

  // Move both until fast falls off the end
  while (fast !== null) {
    fast = fast.next;
    slow = slow.next;
  }

  // slow.next is the node to remove
  slow.next = slow.next.next;

  return dummy.next;
}

// Remove 2nd from end of [1,2,3,4,5] → [1,2,3,5]
console.log(toArray(removeNthFromEnd(buildList([1, 2, 3, 4, 5]), 2)));

Warning

n is guaranteed to be valid (1 ≤ n ≤ list length) in most problem statements. If n could equal the list length, the dummy node ensures that removing the head still works correctly without a special case.

	Time	Space
Two-pointer gap	O(n)	O(1)

6. Intersection of Two Linked Lists

Problem: Find the node where two singly linked lists intersect (by reference, not value). Return null if they do not intersect.

Approach 1 — Length difference: Compute lengths lenA and lenB. Advance the pointer of the longer list by |lenA − lenB| steps so both pointers are the same distance from the end. Then walk together until they meet.

Approach 2 — Two-pointer switcheroo (elegant): When pointer A reaches the end of list A, redirect it to the head of list B. Do the same for B → A. Both pointers travel lenA + lenB total steps. If the lists intersect they meet at the intersection; if not, they both reach null simultaneously.

Two-pointer switcheroo (recommended)

function getIntersectionNode(headA, headB) {
  if (headA === null || headB === null) return null;

  let a = headA;
  let b = headB;

  // Each pointer walks lenA + lenB total nodes.
  // They meet at the intersection, or both hit null (no intersection).
  while (a !== b) {
    a = a === null ? headB : a.next;
    b = b === null ? headA : b.next;
  }

  return a; // intersection node, or null
}

Length-difference approach

function getIntersectionNodeV2(headA, headB) {
  const length = (node) => {
    let len = 0;
    while (node) { len++; node = node.next; }
    return len;
  };

  let lenA = length(headA);
  let lenB = length(headB);
  let a = headA;
  let b = headB;

  // Align starting positions
  while (lenA > lenB) { a = a.next; lenA--; }
  while (lenB > lenA) { b = b.next; lenB--; }

  // Walk together until they meet
  while (a !== b) {
    a = a.next;
    b = b.next;
  }

  return a; // null if no intersection
}

Approach	Time	Space
Two-pointer switcheroo	O(m + n)	O(1)
Length difference	O(m + n)	O(1)

7. Palindrome Linked List

Problem: Return true if the linked list is a palindrome.

Key insight: Split the list in half using slow/fast pointers, reverse the second half in-place, then compare both halves node by node. This achieves O(1) space without converting to an array.

Steps:

Find the middle with slow/fast pointers.
Reverse the second half starting from slow.next.
Compare the first half (head) and the reversed second half.
(Optional) Restore the list.

function isPalindrome(head) {
  if (head === null || head.next === null) return true;

  // Step 1: find the end of the first half
  let slow = head;
  let fast = head;
  while (fast.next !== null && fast.next.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
  }
  // slow is now the last node of the first half

  // Step 2: reverse the second half
  let secondHalf = reverseList(slow.next);

  // Step 3: compare
  let p1 = head;
  let p2 = secondHalf;
  let isPalin = true;
  while (p2 !== null) {
    if (p1.val !== p2.val) { isPalin = false; break; }
    p1 = p1.next;
    p2 = p2.next;
  }

  // Step 4: restore (good practice in interviews)
  slow.next = reverseList(secondHalf);

  return isPalin;
}

// Inline reverseList from problem #1
function reverseList(head) {
  let prev = null, curr = head;
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
}

console.log(isPalindrome(buildList([1, 2, 2, 1]))); // true
console.log(isPalindrome(buildList([1, 2])));        // false

	Time	Space
In-place reversal	O(n)	O(1)

8. Reorder List

Problem: Given list L0 → L1 → … → Ln-1 → Ln, reorder it in-place to L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

Key insight: This problem combines three sub-techniques you already know:

Find the middle (slow/fast pointers).
Reverse the second half (in-place reversal).
Merge alternating nodes from both halves.

Locate the middle: slow/fast pointers give you the split point.
Cut the list: set slow.next = null so the two halves are independent.
Reverse the second half.
Weave: alternate nodes from the first and reversed second half.

function reorderList(head) {
  if (head === null || head.next === null) return;

  // Step 1: find the middle
  let slow = head, fast = head;
  while (fast.next !== null && fast.next.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
  }

  // Step 2: cut and reverse the second half
  let second = slow.next;
  slow.next = null; // cut
  let prev = null;
  while (second !== null) {
    const next = second.next;
    second.next = prev;
    prev = second;
    second = next;
  }
  second = prev; // now the reversed second half

  // Step 3: merge alternating
  let first = head;
  while (second !== null) {
    const tmp1 = first.next;
    const tmp2 = second.next;

    first.next = second;   // first → second
    second.next = tmp1;    // second → rest of first

    first = tmp1;          // advance first pointer
    second = tmp2;         // advance second pointer
  }
}

const list = buildList([1, 2, 3, 4, 5]);
reorderList(list);
console.log(toArray(list)); // [1, 5, 2, 4, 3]

Note

reorderList modifies the list in-place and returns void — the head pointer itself does not change, so the caller keeps their reference to the (now reordered) list.

	Time	Space
Find + reverse + weave	O(n)	O(1)

Pattern Summary

Every problem on this page is solved by mixing at most three building blocks. Recognise the pattern from the problem statement and the solution almost writes itself.

Pattern	When to use	Problems covered
Slow / fast pointers	Find middle, detect cycle, nth from end	#2, #3, #5, #7, #8
In-place reversal	Reverse all or part of a list	#1, #7, #8
Dummy node	Simplify head-insertion edge cases	#4, #5
Two-pointer gap	Fixed-distance relationships	#5, #6
Pointer switcheroo	Equalize path lengths across two lists	#6

Tip

In an interview, state the pattern aloud before writing code. Saying "I'll use slow/fast pointers to find the middle" signals strong pattern recognition and gives your interviewer confidence before you write a single line.