Interview Guide: Linked Lists Problems and Solutions

Understanding Linked Lists

A linked list is a linear data structure where elements, called nodes, are stored in non-contiguous memory locations. Each node contains a data field and a reference (pointer) to the next node in the sequence. Unlike arrays, linked lists do not require contiguous memory allocation, making insertions and deletions efficient without the need to shift elements.

Types of Linked Lists

• Singly Linked List: Each node points only to the next node. Traversal is unidirectional.
• Doubly Linked List: Each node has pointers to both the next and previous nodes, enabling bidirectional traversal.
• Circular Linked List: The last node points back to the head, forming a circle. Can be singly or doubly linked.

Basic Node Structure

In most interview settings, you'll work with a singly linked list node defined like this:

// Java / C++ style
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

# Python style
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

// JavaScript / TypeScript style
class ListNode {
    constructor(val, next = null) {
        this.val = val;
        this.next = next;
    }
}

Why Linked Lists Matter in Technical Interviews

Linked list problems are staples in coding interviews at companies like Google, Meta, Amazon, and Microsoft. They test several fundamental skills simultaneously:

• Pointer manipulation: Can you juggle multiple pointers without losing track of nodes?
• Edge case handling: Empty lists, single-node lists, and off-by-one scenarios
• Iterative vs. recursive thinking: Many linked list problems have elegant solutions in both paradigms
• In-place algorithms: Reversing or rearranging without extra memory demonstrates space-conscious coding
• Cycle detection logic: Floyd's algorithm is a classic that reveals mathematical insight

Interviewers also value linked lists because they reveal whether a candidate truly understands references and memory models—concepts that distinguish novice programmers from experienced engineers.

Core Techniques and Patterns

1. The Dummy Node Pattern

A dummy (sentinel) node simplifies operations where the head might change—like insertion, deletion, or merging. By starting with a dummy node pointing to the real head, you avoid special-case logic for empty or single-element lists.

// Merging two sorted lists using a dummy node
ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;
    
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            tail.next = l1;
            l1 = l1.next;
        } else {
            tail.next = l2;
            l2 = l2.next;
        }
        tail = tail.next;
    }
    
    tail.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

Notice how dummy.next always points to the correct head, regardless of which list was empty initially. The tail pointer builds the merged list node by node.

2. The Two-Pointer (Fast and Slow) Technique

Also known as the tortoise and hare algorithm, this is the go-to approach for cycle detection, finding the middle element, and detecting palindromes. The fast pointer moves twice as fast as the slow pointer.

// Finding the middle node of a linked list
ListNode findMiddle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    
    // For even-length lists, this returns the second middle node
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    return slow;
}

When fast reaches the end, slow is exactly at the midpoint. This runs in O(n) time with O(1) space—dramatically better than counting nodes first.

3. In-Place Reversal

Reversing a linked list in-place is perhaps the most frequently asked linked list question. The key is maintaining three pointers: prev, curr, and a temporary next.

// Iterative reversal of a singly linked list
ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    
    while (curr != null) {
        ListNode nextTemp = curr.next;  // save the next pointer
        curr.next = prev;               // reverse the link
        prev = curr;                    // move prev forward
        curr = nextTemp;                // move curr forward
    }
    
    return prev;  // prev is the new head
}

The recursive version is equally elegant but uses O(n) stack space:

// Recursive reversal
ListNode reverseListRecursive(ListNode head) {
    // Base case: empty list or single node
    if (head == null || head.next == null) {
        return head;
    }
    
    // Recursively reverse the rest of the list
    ListNode reversedRest = reverseListRecursive(head.next);
    
    // Fix the links: the node after head now points back to head
    head.next.next = head;
    head.next = null;
    
    return reversedRest;
}

Essential Interview Problems with Complete Solutions

Problem 1: Detect Cycle in a Linked List (LeetCode 141)

Question: Given a linked list, determine if it contains a cycle. A cycle occurs when a node's next pointer points to an earlier node, creating a loop.

Solution using Floyd's Cycle Detection:

public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }
    
    ListNode slow = head;
    ListNode fast = head;
    
    // Fast pointer moves two steps, slow moves one
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        
        // If they meet, a cycle exists
        if (slow == fast) {
            return true;
        }
    }
    
    // If fast reaches null, no cycle exists
    return false;
}

Time Complexity: O(n) — each pointer traverses at most n nodes.
Space Complexity: O(1) — only two pointers used.

To find the exact node where the cycle begins (LeetCode 142), extend the algorithm:

public ListNode detectCycleStart(ListNode head) {
    if (head == null || head.next == null) return null;
    
    ListNode slow = head, fast = head;
    
    // Phase 1: Find meeting point
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) break;
    }
    
    // No cycle found
    if (fast == null || fast.next == null) return null;
    
    // Phase 2: Reset slow to head, move both at same speed
    slow = head;
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }
    
    return slow;  // This is the cycle start node
}

Problem 2: Merge Two Sorted Linked Lists (LeetCode 21)

Question: Merge two sorted linked lists into one sorted list by splicing nodes together.

Iterative Solution with Dummy Node:

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    // Dummy node to simplify edge cases
    ListNode dummy = new ListNode(0);
    ListNode current = dummy;
    
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }
    
    // Attach remaining nodes (at most one list has leftovers)
    current.next = (l1 != null) ? l1 : l2;
    
    return dummy.next;
}

Recursive Solution:

public ListNode mergeTwoListsRecursive(ListNode l1, ListNode l2) {
    // Base cases: one list is empty
    if (l1 == null) return l2;
    if (l2 == null) return l1;
    
    if (l1.val <= l2.val) {
        l1.next = mergeTwoListsRecursive(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoListsRecursive(l1, l2.next);
        return l2;
    }
}

Time Complexity: O(n + m) where n and m are the lengths of the two lists.
Space Complexity: O(1) iterative, O(n + m) recursive due to call stack.

Problem 3: Remove Nth Node From End of List (LeetCode 19)

Question: Remove the nth node from the end of a linked list and return the head. The constraint is to do it in one pass.

Solution using Two-Pointer Gap Technique:

public ListNode removeNthFromEnd(ListNode head, int n) {
    // Use dummy to handle removal of head gracefully
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    
    ListNode fast = dummy;
    ListNode slow = dummy;
    
    // Advance fast pointer by n+1 steps to create a gap
    for (int i = 0; i <= n; i++) {
        fast = fast.next;
        if (fast == null && i < n) {
            // n is larger than list length
            return head;
        }
    }
    
    // Move both pointers until fast reaches the end
    while (fast != null) {
        slow = slow.next;
        fast = fast.next;
    }
    
    // slow is now just before the node to remove
    slow.next = slow.next.next;
    
    return dummy.next;
}

The gap of n+1 steps ensures that when fast hits null, slow is positioned right before the target node. The dummy node elegantly handles the edge case of removing the head.

Problem 4: Palindrome Linked List (LeetCode 234)

Question: Check if a singly linked list represents a palindrome (reads the same forward and backward).

Solution combining Middle Finding and Reversal:

public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) return true;
    
    // Step 1: Find the middle of the list
    ListNode slow = head;
    ListNode fast = head;
    
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    // Step 2: Reverse the second half of the list
    ListNode prev = null;
    ListNode curr = slow;
    
    while (curr != null) {
        ListNode nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    
    // Step 3: Compare first half with reversed second half
    ListNode left = head;
    ListNode right = prev;  // prev is the head of reversed second half
    
    while (right != null) {
        if (left.val != right.val) {
            return false;
        }
        left = left.next;
        right = right.next;
    }
    
    return true;
}

This solution runs in O(n) time and O(1) space. For even-length lists, the middle pointer naturally lands at the start of the second half.

Problem 5: Intersection of Two Linked Lists (LeetCode 160)

Question: Find the node where two singly linked lists intersect (merge into a common tail). Return null if they don't intersect.

Solution using Length Difference:

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    
    // Count lengths of both lists
    int lenA = 0, lenB = 0;
    ListNode ptrA = headA, ptrB = headB;
    
    while (ptrA != null) {
        lenA++;
        ptrA = ptrA.next;
    }
    while (ptrB != null) {
        lenB++;
        ptrB = ptrB.next;
    }
    
    // Reset pointers to heads
    ptrA = headA;
    ptrB = headB;
    
    // Advance the pointer of the longer list by the difference
    int diff = Math.abs(lenA - lenB);
    if (lenA > lenB) {
        for (int i = 0; i < diff; i++) ptrA = ptrA.next;
    } else {
        for (int i = 0; i < diff; i++) ptrB = ptrB.next;
    }
    
    // Move both pointers together until they meet
    while (ptrA != ptrB) {
        ptrA = ptrA.next;
        ptrB = ptrB.next;
    }
    
    return ptrA;  // Either the intersection node or null
}

Alternative Elegant Solution (Two-Pointer Swap):

public ListNode getIntersectionNodeSwap(ListNode headA, ListNode headB) {
    ListNode ptrA = headA;
    ListNode ptrB = headB;
    
    // Each pointer traverses both lists; they meet at intersection or null
    while (ptrA != ptrB) {
        ptrA = (ptrA == null) ? headB : ptrA.next;
        ptrB = (ptrB == null) ? headA : ptrB.next;
    }
    
    return ptrA;
}

This brilliant trick works because both pointers cover the same total distance: lenA + lenB. If there's an intersection, they meet at the intersection node; otherwise, both become null simultaneously.

Problem 6: Reverse Nodes in k-Group (LeetCode 25)

Question: Reverse the nodes of a linked list k at a time and return the modified list. If the number of nodes is not a multiple of k, leave the leftover nodes as-is.

Solution:

public ListNode reverseKGroup(ListNode head, int k) {
    if (head == null || k == 1) return head;
    
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    
    ListNode groupPrev = dummy;
    
    while (true) {
        // Check if there are at least k nodes remaining
        ListNode check = groupPrev;
        for (int i = 0; i < k && check != null; i++) {
            check = check.next;
        }
        if (check == null) break;  // Less than k nodes left
        
        // Reverse k nodes
        ListNode prev = null;
        ListNode curr = groupPrev.next;
        ListNode groupStart = curr;  // Will become the tail after reversal
        
        for (int i = 0; i < k; i++) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        
        // Connect with the rest of the list
        // prev is the new head of the reversed group
        // curr is the first node after the reversed group
        groupPrev.next = prev;
        groupStart.next = curr;
        
        // Move groupPrev to the tail of the reversed group
        groupPrev = groupStart;
    }
    
    return dummy.next;
}

This is a more advanced problem that combines reversal with careful pointer bookkeeping. The key insight is tracking groupPrev (the node before the current group) and groupStart (which becomes the tail after reversal and must connect to the next group).

Problem 7: Add Two Numbers Represented as Linked Lists (LeetCode 2)

Question: Two non-empty linked lists represent digits of two numbers in reverse order. Add them and return the sum as a linked list.

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode current = dummy;
    int carry = 0;
    
    while (l1 != null || l2 != null || carry != 0) {
        int sum = carry;
        
        if (l1 != null) {
            sum += l1.val;
            l1 = l1.next;
        }
        if (l2 != null) {
            sum += l2.val;
            l2 = l2.next;
        }
        
        carry = sum / 10;
        current.next = new ListNode(sum % 10);
        current = current.next;
    }
    
    return dummy.next;
}

The loop continues even when both lists are exhausted, as long as there's a carry value remaining. This handles cases like 999 + 1 = 1000 cleanly.

Problem 8: Flatten a Multilevel Doubly Linked List (LeetCode 430)

Question: A doubly linked list node may have a child pointer to another doubly linked list. Flatten the list so all nodes appear in a single level.

// Node structure for multilevel list
class Node {
    int val;
    Node prev;
    Node next;
    Node child;
}

public Node flatten(Node head) {
    if (head == null) return null;
    
    Node current = head;
    
    while (current != null) {
        // If current node has a child, process it
        if (current.child != null) {
            // Find the tail of the child list
            Node childTail = current.child;
            while (childTail.next != null) {
                childTail = childTail.next;
            }
            
            // Connect the child's tail to current.next
            childTail.next = current.next;
            if (current.next != null) {
                current.next.prev = childTail;
            }
            
            // Connect current to the child, and clear child pointer
            current.next = current.child;
            current.child.prev = current;
            current.child = null;
        }
        
        current = current.next;
    }
    
    return head;
}

This problem tests your comfort with doubly linked nodes and complex pointer rewiring. The strategy is to find the tail of each child list and splice it between the parent and the parent's original next node.

Common Edge Cases and Pitfalls

When solving linked list problems, always test your solution against these scenarios:

• Empty list (head is null): Does your code handle null gracefully without NullPointerException?
• Single node list: Operations like reversal and deletion must work correctly when there's only one element.
• Two node list: Cycle detection and middle-finding can behave differently with even counts.
• Head changes: When deleting or reversing, the head of the list changes—ensure the caller gets the correct new head.
• Null terminators: Always set tail.next = null after operations that might leave dangling references.
• Circular references: When reversing groups or flattening, ensure you don't accidentally create cycles.

Best Practices for Linked List Interviews

1. Draw Before You Code

Linked lists are inherently visual. Before writing a single line of code, sketch the list with boxes and arrows on a whiteboard or notepad. Walk through your algorithm step by step on the drawing. This reveals pointer reassignment bugs before they become code bugs.

2. Use Dummy Nodes Liberally

A dummy node eliminates the need for special-case handling when the head changes. It's a zero-cost abstraction that dramatically simplifies code. Interviewers appreciate seeing this pattern—it signals experience.

3. Master the Two-Pointer Technique

Fast/slow pointers solve an entire class of problems: cycle detection, middle finding, nth-from-end removal, and palindrome checking. Know the variations: gap pointers (for nth-from-end), meeting pointers (for cycles), and tandem pointers (for partitioning).

4. Handle Edge Cases First

Begin your solution by checking for null or single-node inputs. This shows the interviewer you think defensively and prevents cascading failures later in the code.

5. Discuss Time and Space Complexity

After writing the solution, explicitly state the complexities. For linked lists, O(n) time and O(1) space is often the gold standard. If you use recursion, mention the O(n) stack space trade-off.

6. Consider the Recursive Approach

Many linked list problems have elegant recursive solutions (reversal, merging, palindrome checking). Even if you code iteratively, mentioning the recursive alternative shows depth of understanding. Be prepared to discuss stack overflow risks for very long lists.

7. Test with a Concrete Example

Before declaring your solution complete, trace through a small example (like a 3-5 node list) with the interviewer. Verbally step through each pointer assignment. This catches off-by-one errors and builds confidence.

8. Clean Up Dangling References

In languages without garbage collection (C/C++), mention that you'd free removed nodes. Even in GC languages, setting node.next = null on removed nodes prevents unintended references and helps the garbage collector.

Time and Space Complexity Reference

Here is a quick reference for common linked list operations and their complexities:

• Access by index: O(n) — must traverse from head
• Insert at head: O(1) — constant time regardless of list size
• Insert at tail (with tail pointer): O(1)
• Insert at tail (without tail pointer): O(n)
• Delete at head: O(1)
• Delete by value: O(n) — must find the node first
• Search: O(n) — linear scan required
• Reverse (iterative): O(n) time, O(1) space
• Cycle detection: O(n) time, O(1) space
• Merge sorted lists: O(n + m) time, O(1) space iterative

Conclusion

Linked list problems are more than just interview hurdles—they teach fundamental skills in pointer manipulation, edge case reasoning, and algorithmic efficiency. The patterns covered in this guide—dummy nodes, fast/slow pointers, in-place reversal, and gap pointers—form a toolkit that will serve you across virtually every linked list question you encounter. Master these patterns, practice the core problems repeatedly, and you'll approach linked list interviews with genuine confidence. Remember: draw first, handle nulls early, use dummy nodes, and always trace through a concrete example. With deliberate practice, what once seemed like a maze of pointers becomes a clear, logical path to the optimal solution.