Tracks

Full-Stack Interview Prep

AI Engineering Roadmap →

LinkedList

36 problems · 40 approaches

← Checklist · All topics →

Reverse a linked listEasy2 approaches

Problem

Given the head of a singly linked list, reverse it and return the new head. Be ready to write it both iteratively and recursively.

Example 1

Input:  1 → 2 → 3 → 4 → 5
Output: 5 → 4 → 3 → 2 → 1

Also asked as: Write a Program to reverse the Linked List. (Both Iterative and recursive)

1. Iterative (three pointers)

Time O(n)Space O(1)

Walk the list re-pointing each node’s next to the previous node.

function reverse(head) {
  let prev = null, cur = head;
  while (cur) {
    const next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
  }
  return prev;
}

2. Recursive

Time O(n)Space O(n) call stack

Reverse the rest, then make the next node point back to the current one.

function reverse(head) {
  if (!head || !head.next) return head;
  const newHead = reverse(head.next);
  head.next.next = head;
  head.next = null;
  return newHead;
}
Detect Loop in linked listEasy2 approaches

Problem

Return true if the linked list has a cycle, meaning some node's next pointer points back to an earlier node. Aim for O(1) extra space.

Example 1

Input:  3 → 2 → 0 → -4 → (back to 2)
Output: true

Example 2

Input:  1 → 2 → null
Output: false

Also asked as: detect and remove loop in a linked list · Write a program to Detect loop in a linked list

1. Floyd's tortoise and hare

Time O(n)Space O(1)

A fast pointer (2×) and slow pointer (1×) meet inside a cycle. O(1) 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;
}

To find the loop start: after meeting, move one pointer to head and advance both 1× — they meet at the entry.

2. Hash set of visited nodes

Time O(n)Space O(n)

First node seen twice is on the loop. Simple, O(n) space.

function hasCycle(head) {
  const seen = new Set();
  for (let n = head; n; n = n.next) {
    if (seen.has(n)) return true;
    seen.add(n);
  }
  return false;
}
Merge 2 sorted Linked ListsEasy2 approaches

Problem

Merge two sorted linked lists into one sorted list by relinking their nodes (do not create new nodes). Return the head of the merged list.

Example 1

Input:  1 → 2 → 4 and 1 → 3 → 4
Output: 1 → 1 → 2 → 3 → 4 → 4

Also asked as: merge two sorted lists · merge k sorted linked lists

1. Iterative with dummy head

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

Splice the smaller current node onto a result list; attach the leftover tail at the end.

function mergeTwoLists(a, b) {
  const dummy = { next: null };
  let tail = dummy;
  while (a && b) {
    if (a.val <= b.val) { tail.next = a; a = a.next; }
    else { tail.next = b; b = b.next; }
    tail = tail.next;
  }
  tail.next = a || b;
  return dummy.next;
}

2. Recursive

Time O(n + m)Space O(n + m) call stack

Pick the smaller head, then recurse on the rest.

function mergeTwoLists(a, b) {
  if (!a) return b;
  if (!b) return a;
  if (a.val <= b.val) { a.next = mergeTwoLists(a.next, b); return a; }
  b.next = mergeTwoLists(a, b.next);
  return b;
}
Remove Nth node from end of Linked ListMedium1 approach

Problem

Remove the nth node from the end of the list and return the head. Try to do it in one pass.

Example 1

Input:  1 → 2 → 3 → 4 → 5, n = 2
Output: 1 → 2 → 3 → 5

Example 2

Input:  1, n = 1
Output: empty list

1. Two pointers, one pass

Time O(n)Space O(1)

Advance a lead pointer n steps, then move both until lead hits the end; trail sits just before the target.

function removeNthFromEnd(head, n) {
  const dummy = { next: head };
  let lead = dummy, trail = dummy;
  for (let i = 0; i < n; i++) lead = lead.next;
  while (lead.next) { lead = lead.next; trail = trail.next; }
  trail.next = trail.next.next;
  return dummy.next;
}
Reverse a linked list in groups of size kMedium1 approach

Problem

Reverse the nodes of the list k at a time and return the new head. In the GfG version a final group shorter than k is also reversed. In the LeetCode version it is left as it is — confirm which one is meant.

Example 1

Input:  1 → 2 → 3 → 4 → 5, k = 2
Output: 2 → 1 → 4 → 3 → 5

Example 2

Input:  1 → 2 → 3 → 4 → 5, k = 3
Output: 3 → 2 → 1 → 4 → 5 (LeetCode) or 3 → 2 → 1 → 5 → 4 (GfG)

Also asked as: Reverse a Linked List in group of Given Size

1. Recursive per group

Time O(n)Space O(n / k) recursion

Reverse the first k nodes; recurse on the rest and attach it to the (now) tail of the reversed group.

function reverseKGroup(head, k) {
  let node = head, count = 0;
  while (node && count < k) { node = node.next; count++; }
  if (count < k) return head;              // fewer than k left: keep as is
  let prev = reverseKGroup(node, k), cur = head;
  for (let i = 0; i < k; i++) {
    const next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
  }
  return prev;
}
Delete the loop in a linked listMedium1 approach

Problem

The list may contain a cycle. Find the node where the cycle starts and break the loop by setting the last node's next to null, leaving a plain list.

Example 1

Input:  1 → 3 → 4 → (back to 3)
Output: 1 → 3 → 4 → null

The cycle starts at node 3.

Also asked as: Write a program to Delete loop in a linked list · Find the starting point of the loop

1. Floyd — find the entry, then break it

Time O(n)Space O(1)

After tortoise/hare meet, move one pointer to head; advance both by 1 until they meet again — that node is the loop start. Walk to the node whose next is the start and null it.

function detectAndRemoveLoop(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next; fast = fast.next.next;
    if (slow === fast) break;
  }
  if (!fast || !fast.next) return head;     // no loop
  slow = head;
  if (slow === fast) { while (fast.next !== slow) fast = fast.next; }
  else { while (slow.next !== fast.next) { slow = slow.next; fast = fast.next; } }
  fast.next = null;
  return head;
}
Remove duplicates from a sorted linked listEasy1 approach

Problem

Given a sorted linked list, delete nodes so that each value appears only once.

Example 1

Input:  1 → 1 → 2 → 3 → 3
Output: 1 → 2 → 3

Also asked as: Remove Duplicates in a sorted Linked List

1. Single pass — skip equal neighbours

Time O(n)Space O(1)

If the next node has the same value, unlink it.

function dedupeSorted(head) {
  let cur = head;
  while (cur && cur.next) {
    if (cur.next.val === cur.val) cur.next = cur.next.next;
    else cur = cur.next;
  }
  return head;
}
Remove duplicates from an unsorted linked listEasy1 approach

Problem

Given an unsorted linked list, keep the first occurrence of each value and delete later duplicates.

Example 1

Input:  5 → 2 → 2 → 4 → 5
Output: 5 → 2 → 4

Also asked as: Remove Duplicates in a Un-sorted Linked List

1. Hash set of seen values

Time O(n)Space O(n)

Keep a set; unlink any node whose value was already seen.

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

Without extra space: for each node, run an inner loop deleting later matches — O(n²).

Move the last element to the frontEasy1 approach

Problem

Move the last node of the linked list to the front and return the new head.

Example 1

Input:  1 → 2 → 3 → 4 → 5
Output: 5 → 1 → 2 → 3 → 4

Also asked as: Write a Program to Move the last element to Front in a Linked List

1. Walk to the second-last node

Time O(n)Space O(1)

Detach the last node, point it at the old head, make it the new head.

function moveLastToFront(head) {
  if (!head || !head.next) return head;
  let secondLast = head;
  while (secondLast.next.next) secondLast = secondLast.next;
  const last = secondLast.next;
  secondLast.next = null;
  last.next = head;
  return last;
}
Add 1 to a number represented as a linked listMedium1 approach

Problem

A non-negative number is stored one digit per node, most significant digit first. Add 1 to it and return the resulting list.

Example 1

Input:  4 → 5 → 6
Output: 4 → 5 → 7

Example 2

Input:  9 → 9 → 9
Output: 1 → 0 → 0 → 0

Also asked as: Add “1” to a number represented as a Linked List

1. Reverse, add carry, reverse back

Time O(n)Space O(1)

Reverse so the least-significant digit is first, add 1 propagating carry, reverse again.

function addOne(head) {
  const rev = (h) => { let p = null; while (h) { const n = h.next; h.next = p; p = h; h = n; } return p; };
  head = rev(head);
  let cur = head, carry = 1;
  while (cur && carry) {
    const sum = cur.val + carry;
    cur.val = sum % 10;
    carry = sum >= 10 ? 1 : 0;
    if (carry && !cur.next) { cur.next = { val: 0, next: null }; }
    cur = cur.next;
  }
  return rev(head);
}
Add two numbers represented by linked listsMedium1 approach

Problem

Two non-negative numbers are stored as linked lists, one digit per node. Return their sum as a linked list in the same format. Confirm the digit order: LeetCode stores the digits in reverse (least significant first), GfG stores them most significant first.

Example 1

Input:  2 → 4 → 3 + 5 → 6 → 4 (reverse order)
Output: 7 → 0 → 8

342 + 465 = 807.

Also asked as: Add two numbers represented by linked lists

1. Digit-by-digit with carry (least-significant first)

Time O(n + m)Space O(max(n, m))

If digits are stored LSB-first, walk both lists adding with carry into a new list. (MSB-first: reverse both, or use two stacks.)

function addTwoNumbers(a, b) {
  const dummy = { val: 0, next: null };
  let tail = dummy, carry = 0;
  while (a || b || carry) {
    const sum = (a?.val || 0) + (b?.val || 0) + carry;
    carry = sum >= 10 ? 1 : 0;
    tail.next = { val: sum % 10, next: null };
    tail = tail.next;
    a = a?.next; b = b?.next;
  }
  return dummy.next;
}
Intersection of two sorted linked lists (by value)Easy1 approach

Problem

Given two sorted linked lists, return a new list of the values present in both, in sorted order.

Example 1

Input:  1 → 2 → 3 → 4 → 6 and 2 → 4 → 6 → 8
Output: 2 → 4 → 6

Also asked as: Intersection of two Sorted Linked List

1. Merge-style two pointers

Time O(n + m)Space O(1) besides output

Advance the smaller head; equal values go to the result list.

function sortedIntersection(a, b) {
  const dummy = { val: 0, next: null };
  let tail = dummy;
  while (a && b) {
    if (a.val < b.val) a = a.next;
    else if (a.val > b.val) b = b.next;
    else { tail.next = { val: a.val, next: null }; tail = tail.next; a = a.next; b = b.next; }
  }
  return dummy.next;
}
Intersection point of two linked lists (shared node)Easy2 approaches

Problem

Two singly linked lists merge at some node and share every node after it (a Y shape). Return that first shared node, or null if they never meet. Compare nodes by identity, not by value.

Example 1

Input:  A: 4 → 1 ↘ 8 → 4 → 5,  B: 5 → 6 → 1 ↗ (same 8)
Output: node 8

Also asked as: Intersection Point of two Linked Lists

1. Two pointers, swap heads at the end

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

Advance pA and pB one step at a time; when one hits null, redirect it to the other list’s head. They meet at the intersection after at most n+m steps (or both at null).

function getIntersectionNode(a, b) {
  let pA = a, pB = b;
  while (pA !== pB) {
    pA = pA ? pA.next : b;
    pB = pB ? pB.next : a;
  }
  return pA; // node or null
}

2. Length difference

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

Measure both lengths, advance the longer list by the difference, then move both together until they match.

function getIntersectionNode(a, b) {
  const len = (h) => { let n = 0; while (h) { n++; h = h.next; } return n; };
  let la = len(a), lb = len(b);
  while (la > lb) { a = a.next; la--; }
  while (lb > la) { b = b.next; lb--; }
  while (a !== b) { a = a.next; b = b.next; }
  return a;
}
Merge sort for linked listsMedium1 approach

Problem

Sort a linked list in O(n log n) time using merge sort: split at the middle, sort both halves, and merge them.

Example 1

Input:  4 → 2 → 1 → 3
Output: 1 → 2 → 3 → 4

Also asked as: Merge Sort For Linked lists

1. Split by slow/fast, sort halves, merge

Time O(n log n)Space O(log n) recursion

Find the middle with a fast/slow walk, cut, recursively sort each half, then merge the two sorted lists. Merge sort is preferred for lists (no random access needed, O(1) extra).

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; }
  const mid = slow.next;
  slow.next = null;
  const L = sortList(head), R = sortList(mid);
  const dummy = { next: null };
  let t = dummy, a = L, b = R;
  while (a && b) {
    if (a.val <= b.val) { t.next = a; a = a.next; } else { t.next = b; b = b.next; }
    t = t.next;
  }
  t.next = a || b;
  return dummy.next;
}
Quicksort for linked listsMedium1 approach

Problem

Sort a linked list using quicksort, partitioning the nodes around a pivot by relinking them.

Example 1

Input:  10 → 30 → 3 → 4 → 20 → 5
Output: 3 → 4 → 5 → 10 → 20 → 30

Also asked as: Quicksort for Linked Lists

1. Partition around the head as pivot

Time O(n log n) avg, O(n²) worstSpace O(log n)

Build two sublists (< pivot, ≥ pivot) in one pass, recursively sort each, then concatenate. Works but merge sort is usually preferred for lists.

function quickSortList(head) {
  if (!head || !head.next) return head;
  const pivot = head.val;
  let less = { next: null }, ge = { next: null };
  let lt = less, gt = ge;
  for (let n = head.next; n; n = n.next) {
    if (n.val < pivot) { lt.next = n; lt = n; } else { gt.next = n; gt = n; }
  }
  lt.next = gt.next = null;
  const sortedLess = quickSortList(less.next);
  const sortedGe = quickSortList(ge.next);
  head.next = sortedGe;
  if (!sortedLess) return head;
  let tail = sortedLess;
  while (tail.next) tail = tail.next;
  tail.next = head;
  return sortedLess;
}
Find the middle element of a linked listEasy1 approach

Problem

Return the middle node of the list. If there are two middle nodes, return the second one.

Example 1

Input:  1 → 2 → 3 → 4 → 5
Output: 3

Example 2

Input:  1 → 2 → 3 → 4 → 5 → 6
Output: 4

Also asked as: Find the middle Element of a linked list

1. Fast/slow pointers

Time O(n)Space O(1)

When fast reaches the end, slow is at the middle (second middle for even length).

function middleNode(head) {
  let slow = head, fast = head;
  while (fast && fast.next) { slow = slow.next; fast = fast.next.next; }
  return slow;
}
Check if a linked list is circularEasy1 approach

Problem

Return true if the list is circular: following next pointers from the head eventually leads back to the head itself (not to some other node).

Example 1

Input:  1 → 2 → 3 → (back to 1)
Output: true

Example 2

Input:  1 → 2 → 3 → null
Output: false

Also asked as: Check if a linked list is a circular linked list

1. Walk until you return to head or hit null

Time O(n)Space O(1)

A circular list’s traversal comes back to head; a normal list ends in null.

function isCircular(head) {
  if (!head) return true;
  let n = head.next;
  while (n && n !== head) n = n.next;
  return n === head;
}
Split a circular linked list into two halvesMedium1 approach

Problem

Split a circular linked list into two circular lists of equal size. If the length is odd, the first list gets one extra node.

Example 1

Input:  1 → 2 → 3 → 4 → 5 → (1)
Output: 1 → 2 → 3 → (1) and 4 → 5 → (4)

Also asked as: Split a Circular linked list into two halves

1. Fast/slow to find the split, then close both loops

Time O(n)Space O(1)

Advance slow by 1 and fast by 2 around the circle; slow ends at the end of the first half. Point each half’s tail back to its own head.

function splitCircular(head) {
  if (!head || head.next === head) return [head, null];
  let slow = head, fast = head;
  while (fast.next !== head && fast.next.next !== head) { slow = slow.next; fast = fast.next.next; }
  if (fast.next.next === head) fast = fast.next;   // even length
  const head2 = slow.next;
  slow.next = head;        // close first half
  fast.next = head2;       // close second half
  return [head, head2];
}
Check whether a singly linked list is a palindromeEasy1 approach

Problem

Return true if the list's values read the same forwards and backwards. Aim for O(n) time and O(1) extra space.

Example 1

Input:  1 → 2 → 2 → 1
Output: true

Example 2

Input:  1 → 2
Output: false

Also asked as: Write a Program to check whether the Singly Linked list is a palindrome or not

1. Reverse the second half, compare, restore

Time O(n)Space O(1)

Find the middle, reverse the second half, walk both halves in lockstep comparing values (optionally re-reverse to restore).

function isPalindrome(head) {
  let slow = head, fast = head;
  while (fast && fast.next) { slow = slow.next; fast = fast.next.next; }
  let prev = null;
  while (slow) { const n = slow.next; slow.next = prev; prev = slow; slow = n; }
  let a = head, b = prev, ok = true;
  while (b) { if (a.val !== b.val) { ok = false; break; } a = a.next; b = b.next; }
  return ok;
}
Reverse a doubly linked listEasy1 approach

Problem

Reverse a doubly linked list by swapping each node's prev and next pointers, and return the new head.

Example 1

Input:  1 ⇄ 2 ⇄ 3 ⇄ 4
Output: 4 ⇄ 3 ⇄ 2 ⇄ 1

Also asked as: Reverse a Doubly Linked list

1. Swap prev/next for every node

Time O(n)Space O(1)

For each node swap its prev and next pointers; the old tail becomes the new head.

function reverseDLL(head) {
  let cur = head, newHead = head;
  while (cur) {
    [cur.prev, cur.next] = [cur.next, cur.prev];
    newHead = cur;
    cur = cur.prev; // the old next
  }
  return newHead;
}
Find pairs with a given sum in a sorted doubly linked listEasy1 approach

Problem

Given a sorted doubly linked list of distinct values and a target x, return every pair of nodes whose values sum to x. Use O(1) extra space.

Example 1

Input:  1 ⇄ 2 ⇄ 4 ⇄ 5 ⇄ 6 ⇄ 8 ⇄ 9, x = 7
Output: (1, 6), (2, 5)

Also asked as: Find pairs with a given sum in a DLL

1. Two pointers from both ends

Time O(n)Space O(1)

Start one pointer at head, one at tail. Move them inward based on whether the pair sum is below or above the target.

function pairsWithSum(head, target) {
  let tail = head;
  while (tail && tail.next) tail = tail.next;
  let lo = head, hi = tail;
  const res = [];
  while (lo && hi && lo !== hi && hi.next !== lo) {
    const s = lo.val + hi.val;
    if (s === target) { res.push([lo.val, hi.val]); lo = lo.next; hi = hi.prev; }
    else if (s < target) lo = lo.next;
    else hi = hi.prev;
  }
  return res;
}
Count triplets in a sorted DLL with a given sumMedium1 approach

Problem

Given a sorted doubly linked list of distinct values and a target x, count the triplets of nodes whose values sum to x.

Example 1

Input:  1 ⇄ 2 ⇄ 4 ⇄ 5 ⇄ 6 ⇄ 8 ⇄ 9, x = 17
Output: 2

(2, 6, 9) and (4, 5, 8).

Also asked as: Count triplets in a sorted DLL whose sum is equal to given value “X”

1. Fix one node, two-pointer the rest

Time O(n²)Space O(1)

For each node as the smallest of the triplet, run the "pair with sum (X − node.val)" two-pointer scan on the remainder.

function countTriplets(head, x) {
  let tail = head;
  while (tail && tail.next) tail = tail.next;
  let count = 0;
  for (let cur = head; cur; cur = cur.next) {
    let lo = cur.next, hi = tail;
    while (lo && hi && lo !== hi && hi.next !== lo) {
      const s = cur.val + lo.val + hi.val;
      if (s === x) { count++; lo = lo.next; hi = hi.prev; }
      else if (s < x) lo = lo.next;
      else hi = hi.prev;
    }
  }
  return count;
}
Sort a k-sorted doubly linked listMedium1 approach

Problem

Every node in the doubly linked list is at most k positions away from where it belongs in sorted order. Sort the list efficiently.

Example 1

Input:  3 ⇄ 6 ⇄ 2 ⇄ 12 ⇄ 56 ⇄ 8, k = 2
Output: 2 ⇄ 3 ⇄ 6 ⇄ 8 ⇄ 12 ⇄ 56

Also asked as: Sort a “k”sorted Doubly Linked list

1. Min-heap of size k+1

Time O(n log k)Space O(k)

Each element is at most k positions from its sorted spot, so a sliding min-heap of size k+1 yields elements in order.

function sortKSortedDLL(head, k) {
  const heap = [];                    // simple sorted array as a min-heap
  const push = (v) => { let i = heap.findIndex((x) => x > v); i === -1 ? heap.push(v) : heap.splice(i, 0, v); };
  let node = head;
  for (let i = 0; i <= k && node; i++) { push(node.val); node = node.next; }
  let write = head;
  while (heap.length) {
    write.val = heap.shift();
    write = write.next;
    if (node) { push(node.val); node = node.next; }
  }
  return head;
}
Rotate a doubly linked list by N nodesEasy1 approach

Problem

Rotate the doubly linked list counter-clockwise by N nodes: the first N nodes move to the end, in order.

Example 1

Input:  a ⇄ b ⇄ c ⇄ d ⇄ e, N = 2
Output: c ⇄ d ⇄ e ⇄ a ⇄ b

Also asked as: Rotate DoublyLinked list by N nodes · Rotate a Doubly Linked list in group of Given Size

1. Re-link at the Nth boundary

Time O(n)Space O(1)

Walk to node N; the node after it becomes the new head; splice the first N nodes onto the tail.

function rotateDLL(head, n) {
  if (!head || n === 0) return head;
  let cur = head;
  for (let i = 1; i < n && cur; i++) cur = cur.next;
  if (!cur || !cur.next) return head;
  const newHead = cur.next;
  let tail = newHead;
  while (tail.next) tail = tail.next;
  tail.next = head; head.prev = tail;
  newHead.prev = null;
  cur.next = null;
  return newHead;
}
Delete nodes that have a greater value on the right sideMedium1 approach

Problem

Delete every node that has some node with a greater value anywhere to its right. Return the resulting list.

Example 1

Input:  12 → 15 → 10 → 11 → 5 → 6 → 2 → 3
Output: 15 → 11 → 6 → 3

Also asked as: Delete nodes which have a greater value on right side

1. Reverse, keep a running max, reverse back

Time O(n)Space O(1)

After reversing, sweep once keeping the max seen so far; drop any node smaller than that max. Reverse again.

function deleteSmallerOnRight(head) {
  const rev = (h) => { let p = null; while (h) { const n = h.next; h.next = p; p = h; h = n; } return p; };
  head = rev(head);
  let maxSoFar = head, cur = head;
  while (cur && cur.next) {
    if (cur.next.val < maxSoFar.val) cur.next = cur.next.next;
    else { cur = cur.next; maxSoFar = cur; }
  }
  return rev(head);
}
Segregate even and odd nodes in a linked listEasy1 approach

Problem

Rearrange the list so that all even-valued nodes come before all odd-valued nodes, keeping the original relative order within each group.

Example 1

Input:  17 → 15 → 8 → 12 → 10 → 5 → 4
Output: 8 → 12 → 10 → 4 → 17 → 15 → 5

Also asked as: Segregate even and odd nodes in a Linked List

1. Two chains, then join

Time O(n)Space O(1)

Build an even-value chain and an odd-value chain in one pass; append odd after even.

function segregateEvenOdd(head) {
  const evenD = { next: null }, oddD = { next: null };
  let e = evenD, o = oddD;
  for (let n = head; n; n = n.next) {
    if (n.val % 2 === 0) { e.next = n; e = n; } else { o.next = n; o = n; }
  }
  e.next = oddD.next;
  o.next = null;
  return evenD.next;
}
Sort a linked list of 0s, 1s and 2sEasy1 approach

Problem

The list's values are only 0, 1 and 2. Sort it.

Example 1

Input:  1 → 2 → 2 → 1 → 2 → 0 → 2 → 2
Output: 0 → 1 → 1 → 2 → 2 → 2 → 2 → 2

Also asked as: Sort a LL of 0's, 1's and 2's

1. Count and overwrite

Time O(n)Space O(1)

Count 0s/1s/2s in one pass, then rewrite the node values.

function sort012List(head) {
  const c = [0, 0, 0];
  for (let n = head; n; n = n.next) c[n.val]++;
  let n = head;
  for (let v = 0; v < 3; v++) while (c[v]-- > 0) { n.val = v; n = n.next; }
  return head;
}

To rewire pointers instead of values: build three sublists (0s, 1s, 2s) and concatenate.

Flatten a linked list (each node has a bottom sub-list)Medium1 approach

Problem

Each node of a main list has a next pointer (to the next head) and a bottom pointer (to a sorted sub-list). The heads are also in sorted order. Flatten everything into a single sorted list linked through bottom.

Example 1

Input:  5(→7→8→30) → 10(→20) → 19(→22→50) → 28(→35→40→45)
Output: 5 7 8 10 19 20 22 28 30 35 40 45 50

Also asked as: Flatten a Linked List

1. Merge sub-lists from right to left

Time O(n·m) mergesSpace O(n) recursion

Recursively flatten the rest, then merge the current node’s sorted bottom-list with it.

function flatten(head) {
  if (!head || !head.next) return head;
  const merge = (a, b) => {
    const d = { bottom: null }; let t = d;
    while (a && b) {
      if (a.val <= b.val) { t.bottom = a; a = a.bottom; } else { t.bottom = b; b = b.bottom; }
      t = t.bottom;
    }
    t.bottom = a || b;
    return d.bottom;
  };
  head.next = flatten(head.next);
  return merge(head, head.next);
}
Clone a linked list with next and random pointersMedium1 approach

Problem

Each node has next and a random pointer that points to any node in the list, or to null. Create a deep copy: new nodes whose next and random pointers point to the new nodes in the matching positions.

Example 1

Input:  [[7,null], [13,0], [11,4], [10,2], [1,0]]  (value, random index)
Output: An identical structure made of new nodes

Also asked as: Clone a linked list with next and random pointer

1. Interleave copies, wire randoms, split — O(1) space

Time O(n)Space O(1)

Insert each copy right after its original. Then copy.random = original.random.next. Finally unweave the two lists.

function copyRandomList(head) {
  if (!head) return null;
  for (let n = head; n; n = n.next.next) {
    n.next = { val: n.val, next: n.next, random: null };
  }
  for (let n = head; n; n = n.next.next) {
    if (n.random) n.next.random = n.random.next;
  }
  const copyHead = head.next;
  for (let n = head; n; n = n.next) {
    const c = n.next;
    n.next = c.next;
    c.next = c.next ? c.next.next : null;
  }
  return copyHead;
}

Simpler O(n) space: a Map from original node → copy node, two passes.

Merge K sorted linked listsHard1 approach

Problem

Given k sorted linked lists, merge them into one sorted list and return its head.

Example 1

Input:  [1→4→5, 1→3→4, 2→6]
Output: 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6

Also asked as: Merge K sorted Linked list

1. Divide and conquer (pairwise merge)

Time O(N log k)Space O(log k)

Merge lists in pairs, halving the count each round — like merge sort over the array of lists.

function mergeKLists(lists) {
  const merge2 = (a, b) => {
    const d = { next: null }; let t = d;
    while (a && b) { if (a.val <= b.val) { t.next = a; a = a.next; } else { t.next = b; b = b.next; } t = t.next; }
    t.next = a || b;
    return d.next;
  };
  if (!lists.length) return null;
  while (lists.length > 1) {
    const merged = [];
    for (let i = 0; i < lists.length; i += 2)
      merged.push(merge2(lists[i], lists[i + 1] || null));
    lists = merged;
  }
  return lists[0];
}

A min-heap of the k current heads also gives O(N log k).

Multiply two numbers represented by linked listsEasy1 approach

Problem

Two numbers are stored as linked lists, most significant digit first. Return their product, usually modulo 1e9 + 7 because the numbers can be huge.

Example 1

Input:  3 → 2 and 2
Output: 64

Also asked as: Multiply 2 no. represented by LL

1. Build each number, multiply, mod for overflow safety

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

Fold each list into an integer (num = num*10 + digit), multiply. Use modulo 1e9+7 if the problem wants that.

function multiplyLists(a, b) {
  const MOD = 1_000_000_007n;
  const toNum = (h) => { let n = 0n; for (; h; h = h.next) n = (n * 10n + BigInt(h.val)) % MOD; return n; };
  return Number((toNum(a) * toNum(b)) % MOD);
}
Program for n'th node from the end of a linked listEasy1 approach

Problem

Return the value of the nth node from the end of the list, or −1 if the list has fewer than n nodes.

Example 1

Input:  1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9, n = 2
Output: 8

Also asked as: Program for n’th node from the end of a Linked List

1. Two pointers, n apart

Time O(n)Space O(1)

Advance a lead pointer n nodes, then move lead and trail together until lead falls off the end.

function nthFromEnd(head, n) {
  let lead = head;
  for (let i = 0; i < n; i++) { if (!lead) return null; lead = lead.next; }
  let trail = head;
  while (lead) { lead = lead.next; trail = trail.next; }
  return trail;
}
First non-repeating character in a streamMedium1 approach

Problem

Characters arrive one at a time. After each one, report the first character so far that has appeared exactly once, or "#" if there is none.

Example 1

Input:  "aabc"
Output: "a#bb"

After a → a; after aa → #; after aab → b; after aabc → b.

Also asked as: Find the first non-repeating character from a stream of characters · Queue based approach or first non-repeating character in a stream

1. Queue of candidates + frequency count

Time O(1) amortised per charSpace O(k)

Push each new char to a queue and bump its count. Before answering, pop from the front while its count > 1. The front (if any) is the current first non-repeating char.

function firstNonRepeatingStream(chars) {
  const count = new Map(), queue = [];
  const out = [];
  for (const c of chars) {
    count.set(c, (count.get(c) || 0) + 1);
    queue.push(c);
    while (queue.length && count.get(queue[0]) > 1) queue.shift();
    out.push(queue.length ? queue[0] : '#');
  }
  return out.join('');
}
Can we reverse a linked list in less than O(n)? / Why quicksort for arrays, merge sort for lists?Easy1 approach

Problem

Two conceptual questions. (1) Can a singly linked list be reversed faster than O(n)? (2) Why is quicksort preferred for arrays but merge sort for linked lists? Answer each with the reasoning an interviewer expects.

Also asked as: Can we reverse a linked list in less than O(n) ? · Why Quicksort is preferred for. Arrays and Merge Sort for LinkedLists ?

1. Conceptual answers

Time —Space —

No — reversing requires visiting every node to flip its pointer, so it is Θ(n). For sorting: arrays give O(1) random access and cache locality, which quicksort exploits and merge sort wastes (its O(n) auxiliary array + copying hurt). Linked lists have no random access, so quicksort’s partition is awkward and pivots are hard to pick; merge sort splits and merges with only pointer rewiring and O(1) extra space, and is stable — hence the default for lists.

// Reversal is O(n): every node's next pointer must change.
// Merge sort on a list needs no random access and O(1) extra space;
// quicksort on a list can't pick a good pivot cheaply and loses locality.
Deletion from a circular linked listEasy1 approach

Problem

Delete the node with a given value from a circular linked list. Handle the special cases: deleting the head, deleting the only node, and a value that is not present.

Example 1

Input:  2 → 5 → 7 → 8 → 10 → (2), delete 5
Output: 2 → 7 → 8 → 10 → (2)

Also asked as: Deletion from a Circular Linked List

1. Find the node, relink its predecessor

Time O(n)Space O(1)

Walk from head until the next node holds the target value; point current.next past it. If the deleted node is the head, update head (and the last node's next). Handle the single-node case.

function deleteFromCircular(head, key) {
  if (!head) return null;
  if (head.val === key && head.next === head) return null;   // only node
  let last = head;
  while (last.next !== head) last = last.next;               // node before head
  if (head.val === key) { last.next = head.next; return head.next; }
  let cur = head;
  while (cur.next !== head && cur.next.val !== key) cur = cur.next;
  if (cur.next.val === key) cur.next = cur.next.next;
  return head;
}
Reorder ListMedium1 approach

Problem

Reorder L0 → L1 → … → Ln−1 → Ln into L0 → Ln → L1 → Ln−1 → L2 → … in place, by relinking the nodes (do not just change their values).

Example 1

Input:  1 → 2 → 3 → 4 → 5
Output: 1 → 5 → 2 → 4 → 3

1. Middle + reverse + merge

Time O(n)Space O(1)

L0→Ln→L1→Ln−1…: split at the middle (fast/slow), reverse the second half, then weave the two halves together.

function reorderList(head) {
  let slow = head, fast = head;
  while (fast.next && fast.next.next) { slow = slow.next; fast = fast.next.next; }
  let prev = null, cur = slow.next;
  slow.next = null;
  while (cur) { const nx = cur.next; cur.next = prev; prev = cur; cur = nx; }
  let a = head, b = prev;
  while (b) {
    const an = a.next, bn = b.next;
    a.next = b; b.next = an;
    a = an; b = bn;
  }
}