LeetCode (3): Linked List Operations - Reversal, Cycle Detection & Merging

Linked lists are a cornerstone of technical interviews, testing your ability to manipulate pointers, handle edge cases, and optimize space usage. Unlike arrays, linked lists offer insertion and deletion but requirefor access. They naturally support dynamic growth but lack random access capabilities. This comprehensive guide walks through five classic problems —reversing a linked list (iterative and recursive), merging two sorted lists, detecting cycle entry points, finding intersection nodes, and removing the nth node from the end— to build a complete toolkit for linked list mastery. We'll dive deep into the trade-offs between iteration and recursion, the power of dummy nodes, and how to solve complex operations inspace.

Series Navigation

📚 LeetCode Algorithm Series (10 articles total): 1. Hash Tables Complete Guide 2. Two Pointers Technique 3. → Linked List Operations (Reversal, Cycle Detection, Merging, Intersection, Deletion) ← Current Article 4. Binary Tree Traversal and Recursion 5. Dynamic Programming Fundamentals 6. Backtracking Algorithms 7. Advanced Binary Search 8. Stacks and Queues 9. Graph Algorithms 10. Greedy and Bit Manipulation

---

Linked List Fundamentals Review

Linked List vs Array

Feature	Array	Linked List
Access
Insert/Delete (known position)	(requires shifting)
Memory	Contiguous	Non-contiguous
Cache Locality	✅ High	❌ Low
Dynamic Growth	⚠️ Requires reallocation	✅ Natural support

Linked List Node Definition

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

The Mental Model of Linked Lists

Think of a linked list as a train:

• Node: Each train car
• Pointer: The coupling connecting cars
• Head node: The locomotive
• Tail node: The last car (next = None)

Operation Intuition:

• Reverse: Make the train run backward
• Merge: Combine two trains in sorted order
• Detect cycle: Check if the train forms a loop
• Delete node: Remove a car and reconnect the rest

---

LeetCode 206: Reverse Linked List

Problem Description

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

Example:

• Input: head = [1,2,3,4,5]
• Output: [5,4,3,2,1]

Constraints:

• The number of nodes in the list: - Follow-up: Can you solve it both iteratively and recursively?

Approach One: Iterative (Three-Pointer Technique)

Core Idea

Maintain three pointers:

• prev: The previous node
• curr: The current node
• next_node: The next node (temporary storage)

Steps: 1. Initialize prev = None, curr = head 2. Traverse the list, for each iteration:

• Save curr.next to next_node
• Reverse the pointer: curr.next = prev
• Move pointers: prev = curr, curr = next_node

3. Return prev (the new head)

Python Implementation

def reverseList(head):
    """
    Reverse a linked list iteratively using three pointers.
    
    Time Complexity: O(n) - single pass through the list
    Space Complexity: O(1) - only constant extra space
    """
    prev = None
    curr = head
    
    while curr:
        # Save the next node before we lose the reference
        next_node = curr.next
        
        # Reverse the pointer: point current node to previous
        curr.next = prev
        
        # Move both pointers forward
        prev = curr
        curr = next_node
    
    # prev now points to the new head (originally the tail)
    return prev

Complexity Analysis

• Time Complexity:, single traversal
• Space Complexity:, only constant extra pointers

Step-by-Step Walkthrough

Input: 1 → 2 → 3 → None

Step	prev	curr	next_node	Operation	List State
Initial	None	1	-	-	1 → 2 → 3 → None
1	None	1	2	Save 2	-
1	None	1	2	1.next = None	None ← 1 2 → 3 → None
1	1	2	2	Move pointers	-
2	1	2	3	Save 3	-
2	1	2	3	2.next = 1	None ← 1 ← 2 3 → None
2	2	3	3	Move pointers	-
3	2	3	None	Save None	-
3	2	3	None	3.next = 2	None ← 1 ← 2 ← 3
3	3	None	-	Loop ends	-
Return	3	-	-	-	3 → 2 → 1 → None

Common Mistakes and Edge Cases

Mistake 1: Losing the next reference

# ❌ Wrong: We lose the reference to curr.next
curr.next = prev
prev = curr
curr = curr.next  # This is now prev, not the original next!

Mistake 2: Not handling empty list

# ❌ Wrong: If head is None, we return None incorrectly
def reverseList(head):
    prev = None
    curr = head
    while curr:  # This handles None correctly, but be explicit
        # ...

Edge Cases:

• Empty list (head = None): Returns None ✅
• Single node (head = [1]): Returns [1] ✅
• Two nodes (head = [1,2]): Returns [2,1] ✅

Interview Tips

What interviewers look for: 1. Pointer manipulation: Can you safely move pointers without losing references? 2. Edge case handling: Do you check for empty/single-node lists? 3. Space optimization: Can you do it inspace?

Follow-up questions:

• "Can you reverse it recursively?"
• "What if the list has a cycle?"
• "Can you reverse only a portion of the list?"

---

Approach Two: Recursive

Core Idea

Recursive definition: Reversing a list = reverse the rest + adjust current node's pointer

Base case: Empty list or single node, return as is

Recursive steps: 1. Recursively reverse head.next and get the new head new_head 2. Make head.next.next point to head (reverse the pointer) 3. Break head.next (prevent cycle) 4. Return new_head

Python Implementation

def reverseList_recursive(head):
    """
    Reverse a linked list recursively.
    
    The key insight: reverse the rest of the list first,
    then adjust the current node's pointer.
    
    Time Complexity: O(n) - each node visited once
    Space Complexity: O(n) - recursion stack depth
    """
    # Base case: empty list or single node
    if not head or not head.next:
        return head
    
    # Recursively reverse the rest of the list
    # new_head will be the original tail, now the new head
    new_head = reverseList_recursive(head.next)
    
    # At this point, head.next is the last node of the reversed sublist
    # We need to make it point back to head
    head.next.next = head
    
    # Break the original link to prevent cycle
    head.next = None
    
    return new_head

Complexity Analysis

• Time Complexity:, each node visited once
• Space Complexity:, recursion stack depth

Recursive Process Visualization

Input: 1 → 2 → 3 → None

reverseList(1)
    reverseList(2)
        reverseList(3)
            reverseList(None)  # Base case, returns None
        # Now at node 3:
        # 3.next = None, so we return 3
        # Execute: 2.next.next = 2 → 3.next = 2
        # Break: 2.next = None
        # Return 3 (new_head)
    # Now at node 2:
    # Execute: 1.next.next = 1 → 2.next = 1
    # Break: 1.next = None
    # Return 3 (new_head)
# Final: 3 → 2 → 1 → None

Final result: 3 → 2 → 1 → None

Understanding the Recursive Magic

The recursive approach works backward: 1. It first reaches the tail node 2. Then, as the recursion unwinds, it reverses pointers one by one 3. Each level of recursion handles one node reversal

Why head.next.next = head?

• After reversing the sublist starting from head.next, the node originally at head.next is now the tail of the reversed sublist
• We want this tail to point back to head
• head.next.next accesses the node that was originally head.next, and we make it point to head

---

Iterative vs Recursive Comparison

Method	Time	Space	Pros	Cons
Iterative			Space optimal, easier to understand	Slightly longer code
Recursive			Concise, elegant	Stack space overhead, potential stack overflow

Interview Strategy: Start with iterative (more practical), then mention recursive as an alternative approach.

---

LeetCode 21: Merge Two Sorted Lists

Problem Description

Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

Example:

• Input: l1 = [1,2,4], l2 = [1,3,4]
• Output: [1,1,2,3,4,4]

Constraints:

• The number of nodes in both lists: -
• Both lists are sorted in non-decreasing order

Approach One: Iterative (Dummy Node Technique)

Core Idea

Use a dummy node (sentinel node) to simplify boundary handling: 1. Create a dummy node as the predecessor of the result list 2. Use current pointer to track the current build position 3. Compare values of l1 and l2, attach the smaller one to current 4. Handle remaining nodes 5. Return dummy.next (skip the sentinel)

Python Implementation

def mergeTwoLists(l1, l2):
    """
    Merge two sorted linked lists iteratively using dummy node.
    
    The dummy node eliminates the need for special cases when
    building the result list from scratch.
    
    Time Complexity: O(m + n) where m, n are lengths of l1, l2
    Space Complexity: O(1) - only constant extra space
    """
    # Dummy node simplifies boundary handling
    # We'll build the result list after dummy
    dummy = ListNode(-1)
    current = dummy
    
    # Compare and merge while both lists have nodes
    while l1 and l2:
        if l1.val <= l2.val:
            # Attach l1's current node to result
            current.next = l1
            l1 = l1.next
        else:
            # Attach l2's current node to result
            current.next = l2
            l2 = l2.next
        # Move current pointer forward
        current = current.next
    
    # Attach remaining nodes (one list might be exhausted)
    # If l1 is None, l2 has remaining nodes (or None)
    # If l2 is None, l1 has remaining nodes (or None)
    current.next = l1 if l1 else l2
    
    return dummy.next  # Skip the dummy node

Complexity Analysis

• Time Complexity:, whereandare lengths of the two lists
• Space Complexity:, only constant extra pointers

The Power of Dummy Nodes

Why do we need a dummy node?

Without dummy:

# ❌ Need special handling for the first node
def mergeTwoLists_no_dummy(l1, l2):
    if not l1:
        return l2
    if not l2:
        return l1
    
    # Determine the head
    if l1.val <= l2.val:
        head = l1
        l1 = l1.next
    else:
        head = l2
        l2 = l2.next
    
    current = head
    # Now merge the rest...
    # More complex logic needed

With dummy:

# ✅ Unified handling, no special cases
dummy = ListNode(-1)
current = dummy
# Uniform loop logic for all nodes

Real-world analogy: A dummy node is like a "construction marker"— removed after completion, but provides a fixed reference point during construction.

Step-by-Step Walkthrough

Input: l1 = [1,2,4], l2 = [1,3,4]

Step	l1	l2	current	Operation	Result So Far
Initial	1	1	dummy	-	dummy → ...
1	1	1	dummy	Compare: 1 <= 1, attach l1	dummy → 1
1	2	1	1	Move l1 forward	-
2	2	1	1	Compare: 1 < 2, attach l2	dummy → 1 → 1
2	2	3	1	Move l2 forward	-
3	2	3	1	Compare: 2 < 3, attach l1	dummy → 1 → 1 → 2
3	4	3	2	Move l1 forward	-
4	4	3	2	Compare: 3 < 4, attach l2	dummy → 1 → 1 → 2 → 3
4	4	4	3	Move l2 forward	-
5	4	4	3	Compare: 4 <= 4, attach l1	dummy → 1 → 1 → 2 → 3 → 4
5	None	4	4	l1 exhausted, attach rest of l2	dummy → 1 → 1 → 2 → 3 → 4 → 4
Return	-	-	-	Return dummy.next	1 → 1 → 2 → 3 → 4 → 4

Edge Cases

1. One list is empty: l1 = [], l2 = [1,2] → Returns [1,2] ✅
2. Both lists empty: l1 = [], l2 = [] → Returns [] ✅
3. One list longer: l1 = [1], l2 = [2,3,4] → Returns [1,2,3,4] ✅

---

Approach Two: Recursive

Core Idea

Recursive definition:

• If l1.val <= l2.val, result is l1 + merge(l1.next, l2)
• Otherwise, result is l2 + merge(l1, l2.next)

Python Implementation

def mergeTwoLists_recursive(l1, l2):
    """
    Merge two sorted linked lists recursively.
    
    The recursive approach is elegant but uses O(m+n) stack space.
    Choose iterative for production, recursive for interviews to show
    multiple approaches.
    
    Time Complexity: O(m + n)
    Space Complexity: O(m + n) - recursion stack
    """
    # Base cases: if one list is empty, return the other
    if not l1:
        return l2
    if not l2:
        return l1
    
    # Recursive merge: choose the smaller head, then merge the rest
    if l1.val <= l2.val:
        # l1 is smaller, so it becomes the head
        # Recursively merge the rest
        l1.next = mergeTwoLists_recursive(l1.next, l2)
        return l1
    else:
        # l2 is smaller, so it becomes the head
        # Recursively merge the rest
        l2.next = mergeTwoLists_recursive(l1, l2.next)
        return l2

Complexity Analysis

• Time Complexity:
• Space Complexity:, recursion stack

Recursive Visualization

Input: l1 = [1,2], l2 = [3,4]

mergeTwoLists([1,2], [3,4])
    l1.val (1) <= l2.val (3) → True
    l1.next = mergeTwoLists([2], [3,4])
        l1.val (2) <= l2.val (3) → True
        l1.next = mergeTwoLists([], [3,4])
            l1 is None → return [3,4]
        return [2,3,4]
    return [1,2,3,4]

---

LeetCode 142: Linked List Cycle II

Problem Description

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow-up: Can you solve it usingspace?

Example:

• Input: head = [3,2,0,-4], tail connects to node index 1
• Output: Node at index 1

Core Idea: Floyd's Cycle Detection Algorithm (Extended)

Phase 1: Detect if there's a cycle using fast and slow pointers

Phase 2: Find the cycle entrance 1. After meeting, move one pointer back to the start 2. Both pointers move at the same speed (1 step each) 3. The meeting point is the cycle entrance

Python Implementation

def detectCycle(head):
    """
    Find the node where the cycle begins using Floyd's algorithm.
    
    Phase 1: Detect cycle with fast/slow pointers
    Phase 2: Find entrance by moving one pointer to start
    
    Time Complexity: O(n)
    Space Complexity: O(1)
    """
    if not head or not head.next:
        return None
    
    # Phase 1: Detect cycle
    slow = fast = head
    has_cycle = False
    
    while fast and fast.next:
        slow = slow.next        # Move 1 step
        fast = fast.next.next   # Move 2 steps
        
        if slow == fast:
            has_cycle = True
            break
    
    if not has_cycle:
        return None
    
    # Phase 2: Find the entrance
    # Move slow back to head, keep fast at meeting point
    # Both move 1 step at a time
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    
    return slow  # This is the cycle entrance

Mathematical Proof

Let:

• Distance from start to cycle entrance:

• Distance from cycle entrance to meeting point:

• Distance from meeting point to cycle entrance:

• Cycle length: When they meet:

• Slow pointer has traveled:

• Fast pointer has traveled:(whereis the number of extra cycles)

Since fast pointer is twice as fast: $ $

Key insight: Walkingsteps from start reaches entrance = walkingsteps from meeting point reaches entrance.

Sinceis a full cycle, walking from start and meeting point at the same speed will meet at the entrance!

Visual Explanation

Start → [a steps] → Entrance → [b steps] → Meeting Point
                                    ↓
                              [c steps] ←
                                    |
                                    └─── Cycle (L = b + c)

When slow and fast meet:

• Slow: traveled
• Fast: traveled(where)

From the equation:

• If we move slow back to start and both move 1 step at a time
• Slow will travelsteps to reach entrance
• Fast will travelsteps, which also reaches entrance (sinceis full cycles)

Complexity Analysis

• Time Complexity:
• Space Complexity:

Common Mistakes

Mistake 1: Not checking for cycle existence

# ❌ Wrong: Assumes cycle exists
slow = fast = head
while slow != fast:  # This might never terminate if no cycle!
    slow = slow.next
    fast = fast.next.next

Mistake 2: Wrong pointer reset

# ❌ Wrong: Reset fast instead of slow
fast = head  # Should be slow = head
while slow != fast:
    # ...

---

LeetCode 160: Intersection of Two Linked Lists

Problem Description

Given the heads of two singly linked lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection, return null.

Constraints:

• The linked lists have no cycles
• The lists must retain their original structure after the function returns
• Follow-up:time,space

Example:

A:     a1 → a2 ↘
                c1 → c2 → c3
B: b1 → b2 → b3 ↗

Intersection point is c1.

Approach One: Two Pointers (Path Alignment)

Core Idea

Key observation: If two lists intersect, the path from intersection to end has the same length.

Clever trick: 1. Pointer pA traverses A, then jumps to B's start when reaching end 2. Pointer pB traverses B, then jumps to A's start when reaching end 3. The two pointers will meet at intersection (or both reach None)

Why does this work?

Let:

• Length of A's unique part:
• Length of B's unique part:
• Length of common part:
• pA path:
• pB path:They're equal! So they'll reach intersection (or None) simultaneously.

Python Implementation

def getIntersectionNode(headA, headB):
    """
    Find intersection node using two pointers with path switching.
    
    The key insight: if lists intersect, switching paths makes
    both pointers travel the same total distance.
    
    Time Complexity: O(m + n)
    Space Complexity: O(1)
    """
    if not headA or not headB:
        return None
    
    pA, pB = headA, headB
    
    # Both pointers traverse their own list + the other list
    # They'll meet at intersection or both be None
    while pA != pB:
        # If pA reaches end, switch to headB
        # If pB reaches end, switch to headA
        pA = pA.next if pA else headB
        pB = pB.next if pB else headA
    
    # pA and pB are either both None (no intersection)
    # or both pointing to intersection node
    return pA

Complexity Analysis

• Time Complexity:
• Space Complexity:

Step-by-Step Walkthrough

Input:

A: 1 → 2 → 8 → 9
B: 3 → 8 → 9

Step	pA	pB	pA == pB?
0	1	3	❌
1	2	8	❌
2	8	9	❌
3	9	None	❌
4	None	1 (switch to A)	❌
5	3 (switch to B)	2	❌
6	8	8	✅ Meet!

Why This Works: Mathematical Proof

Let:

• Length of list A:
• Length of list B:
• Where= A's unique part,= B's unique part,= common part

After switching:

• pA travels:
• pB travels:Both travel the same distance! If they intersect, they meet at the intersection point. If not, both become None simultaneously.

---

Approach Two: Hash Set

Python Implementation

def getIntersectionNode_hash(headA, headB):
    """
    Find intersection using hash set (simpler but uses O(m) space).
    
    Time Complexity: O(m + n)
    Space Complexity: O(m) or O(n)
    """
    seen = set()
    
    # Traverse A and store all nodes
    curr = headA
    while curr:
        seen.add(curr)
        curr = curr.next
    
    # Traverse B and find first node in set
    curr = headB
    while curr:
        if curr in seen:
            return curr
        curr = curr.next
    
    return None

Complexity

• Time:
• Space:or Comparison: Two-pointer method is space-optimal!

---

LeetCode 19: Remove Nth Node From End of List

Problem Description

Given the head of a linked list, remove the-th node from the end of the list and return its head.

Follow-up: Could you do this in one pass?

Example:

• Input: head = [1,2,3,4,5], n = 2
• Output: [1,2,3,5] (remove the 2nd node from end, which is 4)

Constraints:

• The number of nodes in the list: -

Core Idea: Two Pointers (Gap of n)

Steps: 1. Create a dummy node (handles deletion of head node) 2. Fast pointer movessteps ahead 3. Both pointers move synchronously until fast reaches end 4. Slow pointer is now at the node before the one to delete 5. Delete: slow.next = slow.next.next

Python Implementation

def removeNthFromEnd(head, n):
    """
    Remove the nth node from end using two pointers.
    
    Key insight: maintain n+1 gap between fast and slow pointers.
    When fast reaches end, slow is at node before target.
    
    Time Complexity: O(L) where L is list length - one pass!
    Space Complexity: O(1)
    """
    # Dummy node handles edge case of deleting head
    dummy = ListNode(0)
    dummy.next = head
    
    fast = slow = dummy
    
    # Move fast pointer n+1 steps ahead
    # This ensures slow will be at node BEFORE target
    for _ in range(n + 1):
        fast = fast.next
    
    # Move both pointers synchronously
    while fast:
        fast = fast.next
        slow = slow.next
    
    # Now slow is at node before target
    # Delete the target node
    slow.next = slow.next.next
    
    return dummy.next

Complexity Analysis

• Time Complexity:, whereis list length, one pass
• Space Complexity:

Why Does Fast Pointer Move n+1 Steps?

Goal: Make slow stop at the node before the target node.

Example: head = [1,2,3,4,5], n = 2 (delete 4)

Fast Position	Slow Position	Explanation
dummy → 1 → 2 → 3	dummy	Fast moved 3 steps (n+1)
3 → 4 → 5 → None	dummy → 1 → 2 → 3	Move synchronously
None	3	Slow at 3, can delete 4

Edge Case: Deleting Head Node

Input: head = [1,2], n = 2 (delete 1)

• Fast moves 3 steps: dummy → 1 → 2 → None
• Slow still at dummy
• Delete: dummy.next = 1.next = 2
• Return: dummy.next = 2 ✅

Without dummy: Need special handling for head deletion, code becomes complex!

Common Mistakes

Mistake 1: Wrong gap size

# ❌ Wrong: Only n steps, slow will be AT target, not before
for _ in range(n):
    fast = fast.next
# Now slow.next = slow.next.next will delete wrong node

Mistake 2: Not using dummy

# ❌ Wrong: Need special case for head deletion
if n == length:
    return head.next
# More complex code...

---

LeetCode 23: Merge K Sorted Lists

Problem Description

You are given an array oflinked lists, each linked list is sorted in ascending order. Merge all the linked lists into one sorted linked list and return it.

Example:

• Input: lists = [[1,4,5],[1,3,4],[2,6]]
• Output: [1,1,2,3,4,4,5,6]

Constraints:

- - -

Approach One: Divide and Conquer

Core Idea

Merge lists in pairs recursively, similar to merge sort: 1. Divide: Split the array of lists into two halves 2. Conquer: Recursively merge each half 3. Combine: Merge the two merged halves

Python Implementation

def mergeKLists(lists):
    """
    Merge k sorted lists using divide and conquer.
    
    Time Complexity: O(n log k) where n is total nodes, k is number of lists
    Space Complexity: O(log k) for recursion stack
    """
    if not lists:
        return None
    if len(lists) == 1:
        return lists[0]
    
    mid = len(lists) // 2
    left = mergeKLists(lists[:mid])
    right = mergeKLists(lists[mid:])
    
    return mergeTwoLists(left, right)  # Use our previous merge function

def mergeTwoLists(l1, l2):
    """Helper function from Problem Two"""
    dummy = ListNode(-1)
    current = dummy
    
    while l1 and l2:
        if l1.val <= l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next
    
    current.next = l1 if l1 else l2
    return dummy.next

Complexity Analysis

• Time Complexity:, whereis total nodes,is number of lists
• Space Complexity:, recursion stack depth

Why Divide and Conquer?

Naive approach: Merge lists one by one

• Time:(each merge is, donetimes)

Divide and conquer: Merge in pairs

• Time:(merge tree haslevels, each level processesnodes)

---

Approach Two: Priority Queue (Heap)

Python Implementation

import heapq

def mergeKLists_heap(lists):
    """
    Merge k sorted lists using min heap.
    
    Time Complexity: O(n log k)
    Space Complexity: O(k) for heap
    """
    # Min heap to always get smallest element
    heap = []
    
    # Initialize heap with first node of each list
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))
    
    dummy = ListNode(-1)
    current = dummy
    
    while heap:
        val, idx, node = heapq.heappop(heap)
        current.next = node
        current = current.next
        
        # Add next node from same list if exists
        if node.next:
            heapq.heappush(heap, (node.next.val, idx, node.next))
    
    return dummy.next

---

LeetCode 138: Copy List with Random Pointer

Problem Description

A linked list of lengthis given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list.

Example:

Original: 7 → 13 → 11 → 10 → 1 → None
          ↓    ↓     ↓     ↓    ↓

          -    7     1     11   7

Approach: Two-Pass with Hash Map

Core Idea

1. First pass: Create all new nodes and map old → new
2. Second pass: Connect next and random pointers using the map

Python Implementation

def copyRandomList(head):
    """
    Deep copy a linked list with random pointers.
    
    Two-pass approach:
    1. Create all nodes and build old → new mapping
    2. Connect next and random pointers using map
    
    Time Complexity: O(n)
    Space Complexity: O(n) for hash map
    """
    if not head:
        return None
    
    # Map old nodes to new nodes
    node_map = {}
    
    # First pass: create all nodes
    curr = head
    while curr:
        node_map[curr] = Node(curr.val)
        curr = curr.next
    
    # Second pass: connect pointers
    curr = head
    while curr:
        new_node = node_map[curr]
        # Connect next pointer
        if curr.next:
            new_node.next = node_map[curr.next]
        # Connect random pointer
        if curr.random:
            new_node.random = node_map[curr.random]
        curr = curr.next
    
    return node_map[head]

Complexity Analysis

• Time Complexity:, two passes
• Space Complexity:, hash map storage

---

The Power of Dummy Nodes

When to Use Dummy Nodes?

Signals:

• Might delete head node
• Need to return new head node
• Building new linked list

Benefits:

• Unified handling of head and other nodes
• No special cases for empty lists
• Cleaner code

Comparison Example: Delete Node

Without dummy:

def deleteNode(head, val):
    # ❌ Special case for head
    if head.val == val:
        return head.next
    
    curr = head
    while curr.next:
        if curr.next.val == val:
            curr.next = curr.next.next
            break
        curr = curr.next
    return head

With dummy:

def deleteNode_dummy(head, val):
    dummy = ListNode(0)
    dummy.next = head
    curr = dummy
    
    # ✅ Unified handling
    while curr.next:
        if curr.next.val == val:
            curr.next = curr.next.next
            break
        curr = curr.next
    
    return dummy.next

---

Common Pitfalls and Debugging Tips

Pitfall 1: Null Pointer Access

# ❌ curr might be None
while curr:
    if curr.next.val == target:  # 💥 curr.next might be None
        # ...

Fix:

# ✅ Check if curr.next exists
while curr and curr.next:
    if curr.next.val == target:
        # ...

Pitfall 2: Losing Node Reference After Pointer Modification

# ❌ Wrong example
curr.next = curr.next.next  # Direct skip, lost reference to deleted node

Correct approach:

• If you need to access the deleted node, save it first:

  to_delete = curr.next
  curr.next = curr.next.next
  # Can still use to_delete

Pitfall 3: Forgetting to Move Pointer

# ❌ Infinite loop
while curr:
    # Process logic
    # Forgot: curr = curr.next

Debugging Tips

Tip 1: Print Linked List

def print_list(head):
    vals = []
    curr = head
    while curr:
        vals.append(str(curr.val))
        curr = curr.next
    print(" → ".join(vals) + " → None")

Tip 2: Draw Diagrams

Draw the linked list state at each step, especially when modifying pointers.

Tip 3: Step-by-Step Debugging

For complex operations (like reversal, merging), execute step by step and check pointer state after each step.

---

Linked List Interview Communication Templates

Template 1: Identify Linked List Characteristics

"This problem involves linked list manipulation. Linked lists have insertion/deletion butaccess. I'll use [iterative/recursive] approach with [two pointers/dummy node] technique to [reverse/merge/detect] the list."

Template 2: Choose Iterative vs Recursive

"I can implement this iteratively withspace, or recursively with cleaner code butspace. For production, I prefer iterative to avoid stack overflow; for interviews, I'll show iterative first, then mention recursive as an alternative."

Template 3: Explain Dummy Node

"I'll use a dummy node as a sentinel to unify handling of head node special cases, avoiding complex boundary checks. Finally, return dummy.next."

Template 4: Fast-Slow Pointers

"I'll use fast-slow pointers: fast moves 2 steps, slow moves 1 step. This solves the problem in one pass withtime andspace."

---

❓ Q&A: Linked List Interview Tips

Q1: When should I use recursion vs iteration for linked lists?

A: Use iteration when:

• Space optimization matters (vs)
• Production code (avoid stack overflow risk)
• Long lists (recursion depth concerns)

Use recursion when:

• Code clarity is priority
• Demonstrating multiple approaches in interviews
• Natural recursive structure (e.g., tree-like problems)

Interview tip: Always mention both approaches, but implement iteration first.

---

Q2: How do I handle edge cases systematically?

A: Check these systematically: 1. Empty list: head == None 2. Single node: head.next == None 3. Two nodes: Special cases for operations 4. Head modification: Use dummy node 5. Cycle detection: Check fast and fast.next before accessing

Pattern: Always check node before accessing node.next.

---

Q3: What's the best way to find the middle of a linked list?

A: Use fast-slow pointers:

def findMiddle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

When fast reaches end, slow is at middle (or second middle if even length).

---

Q4: How do I detect a cycle without using extra space?

A: Use Floyd's algorithm (fast-slow pointers):

• Fast moves 2 steps, slow moves 1 step
• If they meet, cycle exists
• To find entrance: move one pointer to start, both move 1 step

Time:, Space:

Q5: What's the trick to deleting a node when you only have access to that node?

A: Copy next node's data, then delete next node:

def deleteNode(node):
    # Can't delete if it's the last node
    if not node.next:
        return
    
    # Copy next node's value
    node.val = node.next.val
    # Delete next node
    node.next = node.next.next

Note: This doesn't work for the last node (requires None).

---

Q6: How do I reverse a linked list in groups of k?

A: Use recursion:

def reverseKGroup(head, k):
    # Check if we have k nodes
    curr = head
    count = 0
    while curr and count < k:
        curr = curr.next
        count += 1
    
    if count == k:
        # Reverse first k nodes
        curr = reverseKGroup(curr, k)  # Recurse for rest
        while count > 0:
            next_node = head.next
            head.next = curr
            curr = head
            head = next_node
            count -= 1
        head = curr
    return head

---

Q7: What's the most common mistake in linked list problems?

A: Accessing node.next when node might be None.

Always check:

if node and node.next:
    # Safe to access node.next

---

Q8: How do I merge k sorted lists efficiently?

A: Two main approaches:

1. Divide and Conquer:time,space

   • Merge pairs recursively

2. Priority Queue:time,space

   • Use min heap to always get smallest element

Both are optimal. Choose based on space constraints.

---

Q9: Can I modify a linked list in-place without extra space?

A: Yes! Most operations can be done inspace:

• Reversal: Three pointers
• Cycle detection: Fast-slow pointers
• Merging: Dummy node + pointers
• Deletion: Two pointers

Key: Use pointers cleverly, avoid extra data structures.

---

Q10: What should I say when asked about time/space complexity?

A: Be specific:

• Time: Count operations (traversals, comparisons)
• Space: Count extra variables (pointers =, recursion stack =, hash map =)

Example: "This uses two pointers, so space is. We traverse once, so time is."

---

Practice Problems (10 Recommended)

Basic Operations

1. Reverse Linked List (LeetCode 206) ← Covered in this article Easy
2. Merge Two Sorted Lists (LeetCode 21) ← Covered in this article Easy
3. Remove Nth Node From End (LeetCode 19) ← Covered in this article Medium

Cycle Detection and Intersection

4. Linked List Cycle (LeetCode 141) Easy
5. Linked List Cycle II (LeetCode 142) ← Covered in this article Medium
6. Intersection of Two Linked Lists (LeetCode 160) ← Covered in this article Easy

Advanced Operations

7. Palindrome Linked List (LeetCode 234) Easy
8. Sort List (LeetCode 148) Medium
9. Reorder List (LeetCode 143) Medium
10. Copy List with Random Pointer (LeetCode 138) ← Covered in this article Medium

---

Summary: Linked List Operations Cheat Sheet

Core Techniques Quick Reference

Technique	Use Case	Example Problems
Two Pointers	Find middle, cycle detection, nth from end	Cycle detection, remove nth node
Dummy Node	Delete head, build new list	Merge lists, delete node
Recursion	Reverse, merge (clean code)	Reverse list, merge lists
Iteration	All operations (space optimal)	Reverse list, detect cycle

When to Use What?

Two Pointers:

• Need to track multiple positions simultaneously
• Cycle detection (fast-slow)
• Find middle, nth from end

Dummy Node:

• Might modify head node
• Building new linked list
• Simplify boundary conditions

Recursion vs Iteration:

• Recursion: Clean code, good for demonstrating algorithm thinking
• Iteration: Space optimal, better for production

Common Pitfalls

1. Null pointer: Check node before accessing node.next
2. Lost reference: Save necessary references before modifying pointers
3. Forgot to move pointer: Every loop branch must move pointer
4. Edge cases: Empty list, single node, head node operations

Interview Golden Phrases

"The core of linked lists is pointer manipulation. I'll use [two pointers/dummy/recursion] technique, ensure boundary safety, achieving time,space (or explainstack space for recursion)."

Memory Mnemonic

Two pointers find cycles and middle, dummy simplifies boundaries, iteration saves space recursion is elegant, pointer operations avoid nulls and pitfalls!

---

Next Article Preview

In LeetCode (4): Binary Tree Traversal and Recursion, we'll explore:

• Four traversal methods: Preorder, inorder, postorder, level-order
• Recursive patterns: Subtree problem decomposition
• Morris traversal:space traversal
• Classic problems: Lowest common ancestor, path sum, tree serialization

Food for thought: How to perform inorder traversal without recursion or stack? Answer in the next article!

---

Further Reading

• Books:
  • Introduction to Algorithms Chapter 10: Linked Lists
  • Cracking the Coding Interview — Linked List Chapter
• Visualization:
  • VisuAlgo - Linked Lists: https://visualgo.net/en/list
• LeetCode: Linked List tag (100+ problems)

Linked lists aren't the "hard part" of data structures — they're the touchstone of pointer thinking. Master them, and you'll easily handle trees, graphs, and more complex structures!