Skip to main content

Linked Lists

Overview​

A linked list is a data structure consisting of a sequence of nodes, where each node contains data and a reference to the next node. Unlike arrays, linked lists excel at dynamic sizing and efficient insertions/deletions, but sacrifice random access capability.

Singly Linked List​

Each node points to the next node, and the last node points to nothing. The start of the list is called the head.

head
 ↓
[1] -> [2] -> [3] -> [4] -> null
 ╰──────────────────────→

Doubly Linked List​

An extended version that allows bidirectional traversal. Each node has references to both the next and previous nodes, making deletion more straightforward.

       head
        ↓
null <-[1]<->[2]<->[3]<->[4]-> null
        ╰───────────────────→
               ←────────────╯

When to Use​

  • Problem explicitly provides a linked list (e.g., "given the head of a linked list")
  • Need dynamic sizing with frequent insertions/deletions
  • Sequential access is sufficient (no random access needed)
  • Problems involving node manipulation (reversal, removal, reordering)
  • Implementing queues, stacks, or LRU caches

Common Techniques​

Dummy Node​

When operations might modify the head of the list (e.g., deletion, insertion at front), create a dummy node that points to the head. This eliminates edge cases where the head itself needs to be removed or changed.

dummy -> [1] -> [2] -> [3] -> null
  ↓
 head

After the operation, return dummy.next as the new head.

Problems​

Linked List Reversal​

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

Example 1:​

Input:  1 -> 2 -> 3 -> 4 -> 5 -> null
Output: 5 -> 4 -> 3 -> 2 -> 1 -> null

Example 2:​

Input:  1 -> 2 -> null
Output: 2 -> 1 -> null

Brute Force Approach​

Store all node values in an array, then reconstruct the linked list by traversing the array in reverse order.

This approach has a time complexity of O(n) but requires O(n) extra space and doesn't reverse the original list in place.

Iterative Approach​

Reverse the list in place by changing each node's next pointer to point to its previous node:

  • Initialize prev_node to null and curr_node to head.
  • At each node:
    • Save a reference to the next node (next_node = curr_node.next).
    • Reverse the pointer (curr_node.next = prev_node).
    • Move both pointers forward (prev_node = curr_node, curr_node = next_node).
  • When curr_node is null, prev_node is the new head.

Complexity:

  • Time complexity: O(n).
  • Space complexity: O(1).

Recursive Approach​

Think of reversal as: reverse the rest of the list first, then fix the current node.

  • Base case: If the node is null or the last node, return it as the new head.
  • Recursive step: Reverse the rest of the list starting from head.next.
  • Fix pointers: Make the next node point back to the current node (head.next.next = head), then disconnect the current node (head.next = null).

The key insight is that after recursion returns, head.next is now the tail of the reversed sublist, so we can use it to append the current node.

Complexity:

  • Time complexity: O(n).
  • Space complexity: O(n) due to the call stack.

Interviewing Tips​

  • Visualize pointer manipulations by drawing out each step.
  • Clarify if the list is singly or doubly linked.
  • Ask about edge cases: empty list, single node.
  • Mention both iterative and recursive approaches, noting the space trade-off.

Remove Kth Node from End​

Given the head of a singly linked list, remove the kth node from the end and return the new head.

Constraint: The linked list contains at least one node.

Example 1:​

Input:  1 -> 2 -> 3 -> 4 -> 5 -> null, k = 2
Output: 1 -> 2 -> 3 -> 5 -> null

Explanation: The 2nd node from the end is 4, which is removed.

Example 2:​

Input:  1 -> 2 -> null, k = 2
Output: 2 -> null

Explanation: The 2nd node from the end is the head itself (1), which is removed.

Brute Force Approach​

First traverse the list to obtain its length, then traverse again to find and remove the target node.

This approach has a time complexity of O(n) but requires two passes through the list.

Two Pointers Approach​

Use two pointers (leader and trailer) to find the kth node from the end in a single pass:

  • Create a dummy node pointing to the head (see Common Techniques).
  • Move leader ahead by k nodes.
  • Move both leader and trailer forward until leader reaches the end.
  • trailer is now just before the target node — remove it by updating trailer.next.
  • Return dummy.next as the new head.

Why use a dummy node? If the head is the node to be removed (e.g., k equals the list length), the dummy node ensures we have a reference before the head to perform the deletion.

Complexity:

  • Time complexity: O(n) — single pass.
  • Space complexity: O(1).

Interviewing Tips​

  • Mention the dummy node technique upfront when deletion is involved.
  • Clarify edge cases: k equals list length (remove head), k equals 1 (remove tail).
  • Draw out the pointer positions to show the k-gap between leader and trailer.
  • Confirm whether k is guaranteed to be valid or if you need to handle invalid inputs.