Linked List — Interview Questions

Assume a node has the following shape unless stated otherwise:

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

1. What is a linked list and how does it differ from an array?

A linked list is a sequence of nodes. Each node stores a value and a reference to the next node; a doubly linked node also points to the previous node.

Operation / property	Array	Linked list
Access by index	$O (1)$	$O (n)$
Insert/delete at a known position	Usually $O (n)$ because elements shift	$O (1)$ once the node is known
Search	$O (n)$	$O (n)$
Memory layout	Contiguous	Nodes may be scattered
Extra memory	Little per element	One or more pointers per node
Cache locality	Good	Poor

Arrays are preferable for random access and cache efficiency. Linked lists are useful when the workload frequently inserts or removes nodes and already has a reference to the affected location.

2. What are the types of linked lists?

Singly linked list: each node points to its successor.
Doubly linked list: each node has both next and prev pointers.
Circular singly linked list: the tail points back to the head.
Circular doubly linked list: tail.next is the head and head.prev is the tail.
Sentinel-based list: dummy head and/or tail nodes remove edge cases from insertion and deletion.

The right type depends on the operations required. For example, an LRU cache uses a doubly linked list because it must remove an arbitrary node in $O (1)$ time.

3. How do you reverse a singly linked list?

Keep three references: the already reversed prefix, the current node, and the untouched suffix. Redirect one next pointer per iteration.

function reverseList(head) {
  let prev = null;
  let curr = head;
 
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
 
  return prev;
}

Time is $O (n)$ and auxiliary space is $O (1)$ . A recursive version also takes $O (n)$ time but consumes $O (n)$ call-stack space.

4. How do you detect a cycle in a linked list (Floyd’s Cycle Detection)?

Move slow one step and fast two steps. If a cycle exists, they must eventually meet inside it. If fast reaches null, the list is acyclic.

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

This takes $O (n)$ time and $O (1)$ space. Compare node identity, not node values.

5. How do you find the middle node of a linked list?

Use a slow pointer that moves once for every two moves of a fast pointer.

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

For an even-length list, this version returns the second middle. It runs in $O (n)$ time and $O (1)$ space.

6. How do you merge two sorted linked lists?

Use a dummy node and repeatedly append the smaller current node. Reuse the existing nodes rather than allocating a new list.

function mergeTwoLists(a, b) {
  const dummy = new ListNode(0);
  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;
}

Time is $O (n + m)$ and auxiliary space is $O (1)$ .

7. How do you find the nth node from the end of a linked list?

Maintain two pointers exactly n nodes apart. When the leading pointer reaches the end, the trailing pointer is at the answer.

function nthFromEnd(head, n) {
  if (n <= 0) return null;
 
  let fast = head;
  let slow = head;
 
  for (let i = 0; i < n; i++) {
    if (!fast) return null; // n is larger than the list
    fast = fast.next;
  }
 
  while (fast) {
    fast = fast.next;
    slow = slow.next;
  }
 
  return slow;
}

This is a one-pass $O (n)$ -time, $O (1)$ -space solution.

8. How do you check if a linked list is a palindrome?

Find the midpoint, reverse the second half, and compare the two halves. Restore the reversed half afterward if callers expect the list to remain unchanged.

function isPalindrome(head) {
  if (!head || !head.next) return true;
 
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
 
  let right = reverseList(slow);
  const secondHalfHead = right;
  let left = head;
  let answer = true;
 
  while (right) {
    if (left.val !== right.val) {
      answer = false;
      break;
    }
    left = left.next;
    right = right.next;
  }
 
  reverseList(secondHalfHead); // restore
  return answer;
}

Time is $O (n)$ and auxiliary space is $O (1)$ .

9. How do you remove duplicates from a sorted linked list?

Because duplicates are adjacent, compare every node with its successor and bypass equal successors.

function deleteDuplicates(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;
}

This retains one copy of every value in $O (n)$ time and $O (1)$ space. If the requirement is to remove all values that have duplicates, use a dummy node because the head may change.

10. How do you find the intersection point of two linked lists?

Let each pointer traverse both lists. Pointer a walks list A then B; pointer b walks B then A. Each therefore covers the same total distance, so they meet at the shared node or both become null.

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

Time is $O (n + m)$ and space is $O (1)$ . Intersection means the same node object, not merely equal values.

11. How do you implement merge sort on a linked list?

Split the list with slow/fast pointers, recursively sort each half, then merge the halves. Merge sort suits linked lists because merging does not require shifting elements or random access.

function sortList(head) {
  if (!head || !head.next) return head;
 
  let slow = head;
  let fast = head.next;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
 
  const rightHead = slow.next;
  slow.next = null;
 
  const left = sortList(head);
  const right = sortList(rightHead);
  return mergeTwoLists(left, right);
}

Time is $O (n lo g n)$ . Merging uses $O (1)$ auxiliary space, while recursion uses $O (lo g n)$ stack space.

12. How do you reverse a linked list in groups of k?

Use a dummy node. Before reversing, verify that a complete group of k nodes remains. Reverse that group in place, connect it to the previous group, and continue.

function reverseKGroup(head, k) {
  if (k <= 1) return head;
 
  const dummy = new ListNode(0, head);
  let groupPrev = dummy;
 
  while (true) {
    let kth = groupPrev;
    for (let i = 0; i < k && kth; i++) kth = kth.next;
    if (!kth) break;
 
    const groupNext = kth.next;
    let prev = groupNext;
    let curr = groupPrev.next;
 
    while (curr !== groupNext) {
      const next = curr.next;
      curr.next = prev;
      prev = curr;
      curr = next;
    }
 
    const oldGroupHead = groupPrev.next;
    groupPrev.next = kth;
    groupPrev = oldGroupHead;
  }
 
  return dummy.next;
}

Time is $O (n)$ and auxiliary space is $O (1)$ . An incomplete final group remains unchanged.

13. How would you add two numbers represented as linked lists?

For digits stored least-significant first, advance through both lists while maintaining a carry. Treat a missing digit as zero.

function addTwoNumbers(a, b) {
  const dummy = new ListNode(0);
  let tail = dummy;
  let carry = 0;
 
  while (a || b || carry) {
    const sum = (a?.val ?? 0) + (b?.val ?? 0) + carry;
    carry = Math.floor(sum / 10);
    tail.next = new ListNode(sum % 10);
    tail = tail.next;
    a = a?.next ?? null;
    b = b?.next ?? null;
  }
 
  return dummy.next;
}

Time and output space are $O (max (n, m))$ . If digits are stored most-significant first, use stacks or reverse both lists first.

14. What is an LRU Cache and how is it implemented with a linked list?

An LRU cache evicts the least recently used entry when it reaches capacity. Combine:

A hash map from key to node for $O (1)$ lookup.
A doubly linked list ordered by recency for $O (1)$ removal and movement.
Dummy head and tail nodes to simplify boundary operations.

The most recently used node sits near the head and the least recently used node near the tail. get(key) moves the found node to the front. put(key, value) inserts or updates at the front, and evicts tail.prev if over capacity. Both operations are $O (1)$ ; storage is $O (c a p a c i t y)$ .

A singly linked list is insufficient because removing an arbitrary cached node would require finding its predecessor.

15. How do you flatten a multilevel doubly linked list?

Each node may have next, prev, and child. A depth-first traversal places the child list immediately after its parent. A stack remembers the original next node while processing the child.

function flatten(head) {
  if (!head) return null;
 
  const dummy = { next: null };
  let prev = dummy;
  const stack = [head];
 
  while (stack.length) {
    const curr = stack.pop();
    prev.next = curr;
    curr.prev = prev === dummy ? null : prev;
 
    if (curr.next) stack.push(curr.next);
    if (curr.child) {
      stack.push(curr.child);
      curr.child = null;
    }
 
    prev = curr;
  }
 
  return dummy.next;
}

Time is $O (n)$ . The explicit stack uses $O (d)$ space, where d is the nesting depth.

16. How do you sort a linked list?

Use merge sort for the general case: split by slow/fast pointers, recursively sort both halves, and merge them. It guarantees $O (n lo g n)$ time and does not need random access; see question 11.

Other choices depend on constraints:

Insertion sort: $O (n^{2})$ , but simple and useful for small or nearly sorted lists.
Counting/bucket sort: potentially $O (n + k)$ when values lie in a small known range.
Quicksort: possible, but partitioning and maintaining tails are awkward, and worst-case time is $O (n^{2})$ .

17. How do you copy a linked list with random pointers?

To achieve $O (1)$ auxiliary space:

Insert each copy directly after its original node.
Set copy.random = original.random?.next.
Detach the interleaved original and copied lists.

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

Time is $O (n)$ . A simpler alternative uses a map from original nodes to copied nodes and requires $O (n)$ extra space.

18. What are the advantages and disadvantages of a doubly linked list over a singly linked list?

Advantages:

Traverse in both directions.
Delete a known node in $O (1)$ without searching for its predecessor.
Insert before or after a known node in $O (1)$ .
Efficiently remove from both ends when head and tail are stored.

Disadvantages:

An extra pointer per node.
More pointer updates for every insertion and deletion.
More opportunities for broken invariants such as node.next.prev !== node.
Usually worse cache behavior and more allocation overhead than arrays.

Use a doubly linked list when backward traversal or arbitrary $O (1)$ removal is important, such as in an LRU cache.

19. How do you detect and remove a loop in a linked list?

First use Floyd’s algorithm to obtain a meeting point. Reset one pointer to the head and advance both one step at a time; their next meeting is the cycle’s entry. Then walk around the cycle to find the node whose next is the entry and set it to null.

function detectAndRemoveLoop(head) {
  let slow = head;
  let fast = head;
 
  do {
    if (!fast || !fast.next) return false;
    slow = slow.next;
    fast = fast.next.next;
  } while (slow !== fast);
 
  slow = head;
  while (slow !== fast) {
    slow = slow.next;
    fast = fast.next;
  }
 
  const cycleStart = slow;
  let cycleTail = cycleStart;
  while (cycleTail.next !== cycleStart) cycleTail = cycleTail.next;
  cycleTail.next = null;
  return true;
}

Time is $O (n)$ and space is $O (1)$ . This also handles a cycle that starts at the head or a self-loop.

20. How do you swap nodes in a linked list without swapping data?

Find each node and its predecessor, redirect the predecessors to the opposite nodes, then swap the two next references. A dummy node handles swaps involving the head.

function swapNodes(head, x, y) {
  if (x === y) return head;
 
  const dummy = new ListNode(0, head);
  let prevX = dummy;
  let prevY = dummy;
 
  while (prevX.next && prevX.next.val !== x) prevX = prevX.next;
  while (prevY.next && prevY.next.val !== y) prevY = prevY.next;
 
  if (!prevX.next || !prevY.next) return dummy.next;
 
  const nodeX = prevX.next;
  const nodeY = prevY.next;
  prevX.next = nodeY;
  prevY.next = nodeX;
  [nodeX.next, nodeY.next] = [nodeY.next, nodeX.next];
 
  return dummy.next;
}

Time is $O (n)$ and space is $O (1)$ . This works for adjacent nodes as well. If values are not unique, identify nodes by reference rather than value.

21. How would you implement a stack and a queue using linked lists?

For a stack, use the head as the top. Both push and pop are $O (1)$ .

class LinkedStack {
  constructor() {
    this.head = null;
  }
 
  push(val) {
    this.head = new ListNode(val, this.head);
  }
 
  pop() {
    if (!this.head) return undefined;
    const val = this.head.val;
    this.head = this.head.next;
    return val;
  }
}

For a queue, keep both head and tail. Enqueue at the tail and dequeue at the head, both in $O (1)$ .

class LinkedQueue {
  constructor() {
    this.head = null;
    this.tail = null;
  }
 
  enqueue(val) {
    const node = new ListNode(val);
    if (!this.tail) this.head = this.tail = node;
    else this.tail = this.tail.next = node;
  }
 
  dequeue() {
    if (!this.head) return undefined;
    const val = this.head.val;
    this.head = this.head.next;
    if (!this.head) this.tail = null;
    return val;
  }
}

22. How do you merge k sorted linked lists efficiently?

Put the head of every non-empty list in a min-heap. Repeatedly remove the smallest node, append it to the result, and insert its successor.

Time: $O (N lo g k)$ , where $N$ is the total number of nodes.
Auxiliary space: $O (k)$ for the heap.

Another strong approach repeatedly merges lists in pairs, like the merge phase of merge sort. It has the same $O (N lo g k)$ time and can use $O (1)$ extra pointer space beyond the input array. Merging lists one at a time can degrade to $O (N k)$ .

23. What is a skip list and how does it improve linked list performance?

A skip list stores several increasingly sparse linked-list levels. Level 0 contains every key; higher levels act as express lanes. Search starts at the highest level, moves right while possible, then drops down.

Random promotion—commonly with probability $1/2$ —keeps the expected height logarithmic:

Expected search, insertion, and deletion: $O (lo g n)$ .
Worst case: $O (n)$ .
Space: $O (n)$ expected.

Skip lists offer ordered-map behavior comparable to a balanced search tree but often have simpler insertion and deletion logic. They are also useful in concurrent data structures because updates can be more localized.

24. How do you rotate a linked list by k positions?

For a right rotation, compute the length, reduce k modulo the length, connect the tail to the head to form a ring, then break the ring at the new tail.

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

Time is $O (n)$ and auxiliary space is $O (1)$ . A left rotation by k is equivalent to a right rotation by length - (k % length).

Interview checklist

Can the head change? Use a dummy node when it removes special cases.
Are you comparing node identity or node values?
Could a cycle make traversal infinite?
Can slow/fast pointers avoid an extra pass or extra memory?
Must the input list be restored after the operation?
Have you handled empty lists, one-node lists, even lengths, and invalid k/n?
State whether space complexity includes output nodes or only auxiliary memory.

Ankit Kashyap

Navigate

Linked List - Interview Questions