Linked list interview questions, with answers

The questions, with answers

1. 1.What is a linked list, and when is it better than an array?

   A linked list is a chain of nodes where each node holds a value and a pointer to the next node; the list is reached through its head. Its strength is cheap structural change: given a pointer to the right spot, inserting or removing a node is O(1) with no shifting, and the list grows without reallocation. Its weakness is access: reaching the k-th element is O(k), there is no binary search, and nodes scattered in memory are unfriendly to the CPU cache, so for most real workloads a dynamic array wins. Choose a list when you insert and delete in the middle far more often than you index, or when you need stable references to nodes — the queue behind a scheduler, the recency chain in an LRU cache.

2. 2.How do you reverse a singly linked list iteratively?

   Walk the list with three pointers — prev, current and next — flipping one link per step: save current.next, point current.next at prev, then advance prev and current. When current becomes null, prev is the new head. It is O(n) time and O(1) extra space, which is why the iterative version is preferred over the recursive one (the recursion uses O(n) stack and overflows on long lists). Edge cases to say out loud: an empty list returns null, and a single node returns itself unchanged.

   Node reverse(Node head) {
       Node prev = null, curr = head;
       while (curr != null) {
           Node next = curr.next;   // save before overwriting
           curr.next = prev;        // flip the link
           prev = curr;             // advance
           curr = next;
       }
       return prev;                 // new head
   }

3. 3.How do you detect a cycle in a linked list, and how do you find where the cycle starts?

   Floyd's algorithm: move a slow pointer one step and a fast pointer two steps. If fast reaches null the list ends, so there is no cycle; if the two pointers ever meet, there is one. Detection is O(n) time and O(1) space, which is the point — a hash set of visited nodes also works but costs O(n) memory.

   Finding the start is the follow-up that separates memorisers from the rest: after the pointers meet, put one back at the head and advance both one step at a time; the node where they meet again is the cycle's first node. It works because the distance from the head to the cycle start equals the distance from the meeting point onward to that same node, modulo the cycle length.

4. 4.How do you find the middle node of a linked list in a single pass?

   Slow and fast pointers again: slow moves one node, fast moves two. When fast reaches the end, slow is at the middle, after one traversal and with O(1) space. The detail interviewers check is the even-length case. With nodes 1 to 6, the loop while (fast != null && fast.next != null) stops slow on node 4 — the second of the two middle nodes. If the problem wants the first middle (node 3), start fast at head.next instead, or stop when fast.next.next is null. State which convention you are using before you write the loop.

   Node middle(Node head) {
       Node slow = head, fast = head;
       while (fast != null && fast.next != null) {
           slow = slow.next;
           fast = fast.next.next;
       }
       return slow;   // second middle for even length
   }

5. 5.How do you find the nth node from the end in one pass?

   Use two pointers separated by n nodes. Advance the first pointer n steps; then move both together until the first pointer runs off the end. The second pointer is now n nodes from the end. One traversal, O(1) space. The edge case is n larger than the length: the first pointer hits null during its head start, and the function should say so rather than dereference null. The two-pass alternative — count the length, then walk to length minus n — is equally O(n) and perfectly acceptable if you explain that the single pass only matters when the list cannot be traversed twice, such as a stream.

6. 6.Can you delete a node when you only have a pointer to that node, not the head?

   Yes, with a trick, as long as it is not the last node: copy the next node's value into this node, then bypass the next node by setting this.next = this.next.next. From the outside the list now looks as if the given node had been removed, in O(1) time with no traversal. The trick fails on the tail — there is no next node to copy from — and in a singly linked list you cannot reach the previous node to unlink the tail properly, so that case genuinely needs the head or a doubly linked list. Mention that the deleted node object is the next one, which matters if other code holds references to nodes.

7. 7.How do you merge two sorted linked lists into one sorted list?

   Keep a dummy head node and a tail pointer. Compare the fronts of the two lists, append the smaller node to the tail, and advance that list; when one list is exhausted, attach the remainder of the other. The dummy node avoids a special case for the first element, and because you relink existing nodes rather than creating new ones, it runs in O(n + m) time with O(1) extra space. This is also the merge step of merge sort on linked lists, which is why merge sort — not quicksort — is the natural sort for a linked list: it never needs random access.

   Node merge(Node a, Node b) {
       Node dummy = new Node(0), tail = dummy;
       while (a != null && b != null) {
           if (a.val <= b.val) { tail.next = a; a = a.next; }
           else                { tail.next = b; b = b.next; }
           tail = tail.next;
       }
       tail.next = (a != null) ? a : b;   // whichever is left
       return dummy.next;
   }

8. 8.How does an LRU cache use a linked list?

   An LRU cache needs two things in O(1): look a key up, and move the item you just used to the "most recent" end while evicting from the "least recent" end. A hash map gives the lookup; a doubly linked list gives the ordering. The map stores key to node, every node sits in the list in recency order, and on each access you unlink the node from wherever it is and reinsert it at the head — O(1) only because the list is doubly linked, so the node knows its predecessor. Eviction pops the tail. A singly linked list would make the unlink O(n), which is the point interviewers probe: why doubly, and why a dummy head and tail make the unlink code free of null checks.

How the diagnostic asks it

One question from the DSA bank, exactly as a sitting would show it. The bank has 4 on linked lists and 60 across DSA.