Introduction

Linked lists are a common topic in coding interviews. Below are five highly frequent linked list problem patterns from LeetCode, each representing a twist on basic list operations. We outline the variant name, the modified pointer technique (how it differs from basic traversal), and an example problem with a step-by-step solution.

Linked List Variants

1. In-Place Reversal of a Linked List

Modified Template: Instead of a standard forward traversal, this pattern reverses the direction of next pointers as it iterates. It uses three pointers: prev, curr, and next. Initially prev = null and curr = head. At each step, store curr.next in next, then redirect curr.next to prev (reversing the link), and move prev and curr one step forward. This in-place pointer flip continues until all nodes point backwards (medium.com). The new head will be the original tail (prev at loop end).

In-place reversal of a singly linked list. Initially, prev = ∅ and curr = 1. The pointer from 1 is flipped to point to null (new tail). Subsequently, each node’s next is reversed in turn (2’s next points to 1, 3’s next points to 2, etc.), resulting in a fully reversed list.

Example Problem: LeetCode 206 – Reverse Linked List – Given the head of a singly linked list, reverse the list and return the new head.

// Java Solution Code
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode nextTemp = curr.next; // Store next node
        curr.next = prev;           // Reverse current node's pointer
        prev = curr;                // Move prev one step forward
        curr = nextTemp;            // Move curr one step forward
    }
    return prev; // prev will be the new head
}

💡 Variants: Reversing sub-parts of a list follows a similar template with pointer adjustments. For example, Reverse Nodes in k-Group reverses every k nodes by repeatedly applying this technique on sublists. It requires tracking the nodes before and after each segment to reconnect the reversed parts.

2. Fast & Slow Pointers (Tortoise & Hare Technique)

Modified Template: This pattern introduces two pointers moving at different speeds through the list. A slow pointer moves one node at a time, and a fast pointer moves two nodes at a time (blog.algomaster.io). By advancing differently, we can detect certain properties:

• In a cyclic list, the fast pointer will eventually lap the slow pointer and meet it if a cycle exists (blog.algomaster.io).
• In a non-cyclic list, the fast pointer reaches the end (null) while slow is at the middle node.

This technique thus helps in cycle detection, finding the middle of a list, checking palindromes, etc., all in one pass.

Fast & slow pointer illustration: the fast pointer (blue) moves two steps at a time, while the slow pointer (green) moves one step. In a cyclic linked list, the fast pointer will eventually catch up to the slow pointer, indicating a cycle. (blog.algomaster.io)

Example Problem: LeetCode 141 – Linked List Cycle – Determine if a linked list contains a cycle (a node that links back to a previous node). Use O(1) extra space.

// Java Solution Code
public boolean hasCycle(ListNode head) {
    if (head == null) return false;
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true; // Pointers meet, cycle exists
    }
    return false; // Fast pointer reached end, no cycle
}

💡 Variants: The fast/slow pattern also finds the middle node of a list by stopping when fast hits the end (medium.com). It is used in palindrome checks (find mid, reverse second half, compare) and finding the cycle start (Floyd’s cycle algorithm extension). These use the same two-pointer concept with slight modifications in post-processing.

3. Two-Pointer Offset (Nth-from-End Technique)

Modified Template: This uses two pointers starting together but then offsetting one by n steps. By the time the leading pointer hits the end, the trailing pointer will be at the (n+1)th last node. This pattern is commonly used to remove or find the k-th node from the end in one pass (medium.com). A dummy head is often used to simplify edge cases where the head might be removed.

Procedure: Initialize two pointers fast and slow at the head. Advance fast by n nodes. Then move both fast and slow one step at a time until fast reaches the end (null). At that point, slow is right before the target node. Adjust pointers to remove or return the target node as needed (medium.com).

Example Problem: LeetCode 19 – Remove Nth Node From End of List – Remove the n-th node from the end of a linked list and return the head of the modified list.

// Java Solution Code
public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode slow = dummy;
    ListNode fast = dummy;

    // Move fast n+1 steps ahead
    for (int i = 0; i <= n; i++) {
        if (fast == null) { // Handles cases where n is too large or list is short
             return head; // Or throw error, depending on problem spec for invalid n
        }
        fast = fast.next;
    }

    // Move both pointers until fast reaches the end of the list
    while (fast != null) {
        slow = slow.next;
        fast = fast.next;
    }

    // Now slow is the node just before the Nth node from the end
    if (slow != null && slow.next != null) {
        slow.next = slow.next.next; // Skip the Nth node
    }
    
    return dummy.next;
}

💡 Variants: The two-pointer offset pattern also helps find the k-th node from the end (without removal). A related trick is finding the intersection of two linked lists: by advancing two pointers and then resetting one to the other list’s head, they align after the length difference and meet at the intersection node (medium.com). Both techniques rely on offsetting pointer positions to sync up at a target.

4. Dummy Head & Sorted Merge Pattern

Modified Template: Many list problems are easier if you use a dummy head (sentinel) to handle edge cases uniformly. In merging or constructing new lists, the dummy’s next will eventually be the real head of the result. Maintain a tail pointer starting at the dummy. Iterate through input lists, and at each step, attach the next node to tail.next and advance tail. This avoids having to treat the first node as a special case since the dummy precedes the result list (medium.com).

Example Problem: LeetCode 21 – Merge Two Sorted Lists – Merge two sorted linked lists into one sorted list.

// Java Solution Code
public 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;
    }

    // Attach whichever list remains
    if (l1 != null) {
        tail.next = l1;
    } else {
        tail.next = l2;
    }

    return dummy.next;
}

💡 Variants: Using a dummy head simplifies list insertion and combination problems. It appears in adding numbers represented by lists (to build the sum list) (medium.com, medium.com), in partitioning a list (building two sublists then joining), and in many merge-related tasks. The dummy is a convenient placeholder to avoid handling empty-result or head-update cases separately.

5. Cloning a List with Random/Arbitrary Pointers

Modified Template: This covers linked lists that have extra pointers besides the normal next (e.g. a random pointer that can point to any node or null). The challenge is to copy the complex pointers structure. A typical solution uses multiple passes with pointer manipulation:

1. Interweave clone nodes: For each original node, create a new node and insert it right after the original node in the list (algo.monster). This weaves the original and cloned nodes in one list.
2. Set random pointers: Traverse the interwoven list and for each original node, set its clone’s random pointer. If original’s random points to node X, then clone’s random should point to X’s clone (which is X.next in the interwoven list) (algo.monster).
3. Detach the clone list: Restore the original list and extract the cloned nodes by reconnecting clone nodes together in their own list (algo.monster).

Example Problem: LeetCode 138 – Copy List with Random Pointer – Each list node has an additional random pointer to any node (or null). Return a deep copy of the list.

# Python Solution Code
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return None

        # 1. Interleave cloned nodes with original nodes
        curr = head
        while curr:
            newNode = Node(curr.val)
            newNode.next = curr.next
            curr.next = newNode
            curr = newNode.next
        
        # 2. Set random pointers of clones
        curr = head
        while curr:
            if curr.random:
                curr.next.random = curr.random.next # curr.random.next is the clone of curr.random
            curr = curr.next.next # Move to the next original node
            
        # 3. Detach the clone list from the original list
        curr = head
        clone_head = head.next
        while curr:
            clone_node = curr.next
            curr.next = clone_node.next # Restore original list's next pointer
            
            if clone_node.next:
                clone_node.next = clone_node.next.next # Set clone list's next pointer
            
            curr = curr.next # Move to the next original node
            
        return clone_head

💡 Variants: Flattening a multilevel linked list (where each node may have a child list) is another pointer-intensive problem. It can be solved by traversing depth-first and splicing child lists into the main list (medium.com, medium.com). Design problems like LRU Cache use a doubly-linked list with extra pointers for quick eviction. Whenever nodes have additional pointers or multi-level structure, the solution often involves carefully updating those pointers in-place (sometimes using a stack or dummy nodes) to achieve the desired list transformation.

Sources: Key patterns and examples are drawn from popular LeetCode interview questions (linkedin.com, linkedin.com) and canonical solutions (medium.com, medium.com, medium.com, medium.com). Techniques like fast/slow pointers and in-place reversal are well-documented for cycle detection (blog.algomaster.io) and list manipulation (blog.algomaster.io). The random-pointer cloning strategy is described in-depth in problem explanations (algo.monster, algo.monster). These patterns cover the most frequent and insightful Linked List variations seen in coding interviews.

Interactive Linked List Animations