ReviseAlgo Logo

Linked Lists

Reversal & Merging

Master in-place Linked List reversals, merging sorted lists, and K-way merge using min-priority queues.

Last Updated: August 2, 2026 • 20 min read

1. Introduction

What are Reversal and Merging?

Reversal and Merging are the two most common structural transformations applied to linked lists:
  • In-place Reversal: Flipping all pointer direction links to reverse the ordering of elements without allocating new nodes.
  • Sorted Merging: Interleaving elements from two or more pre-sorted lists into a single sorted list.

    • Why study them?

    These operations are standard interview building blocks. Advanced questions—like sorting a list in-place (Merge Sort on Linked List) or reversing nodes in K-sized groups—directly compose these two operations.

    Where is it Used?

  • Sort-Merge Joins: Relational database query engines merging table indexes.
  • Event Rollbacks: Undoing sequences of pointer updates in collaborative editors.

    • 2. Mental Models

    Reversing: Turning Arrows

    Imagine you have cards on a table connected by string arrows: 1 -> 2 -> 3. To reverse the list in place, you do not move the cards. Instead, you pick up one arrow at a time and point it backwards: 1. Break the arrow pointing from 2 to 3. 2. Point it from 2 to 1. 3. To do this safely, you need three hands: one on the current card (curr), one on the previous card (prev), and one holding the next card (next) so it doesn't get lost.

    Merging: Zip Fastener

    Imagine zipping two jackets together. You compare the teeth of both zippers, selecting the smaller tooth first, linking it to the output chain, and advancing.

    3. Core Algorithms & Implementations

    1. In-place Reversal (3-Pointer Technique)

    We maintain three pointers: prev (starts at null), curr (starts at head), and nextTemp. In each step, we save the next node, point curr.next to prev, and advance both prev and curr forward.

    2. Merging Two Sorted Lists

    We use a dummy head node. We compare l1.val and l2.val, link the smaller node to curr.next, and advance that list's pointer. At the end, we append any remaining nodes.

    4. Visual Trace: In-Place Reversal Pointer Updates

    Let's reverse 10 -> 20 -> 30:

    5. Real-World Applications

  • External Sorting Merge Phases: Zipping multiple sorted data segments from disk blocks into a single output file stream.
  • Browser History Replay: Iterating backwards through navigation nodes to reconstruct state transitions.

    • 6. Interview Perspective

    How Interviewers Ask This Topic

    Interviewers test advanced combinations:
  • "Reverse a linked list from position M to N." -> Traverse to position M, keep track of boundary nodes, run standard reversal loop for N-M steps, then stitch ends.
  • "Merge K sorted linked lists." -> Push heads into a Min-Heap (priority queue) of size K. Pop the smallest head, append to the output, and push its successor back to heap. Runs in O(N log K) time.

    • Common Mistakes

    Warning: 1. Cyclic References: Forgetting to initialize prev = null. The first node (head) must point to null after reversal. If it points to itself or remains connected to node 2, you create a infinite loop/cycle.
    > 2. Memory Leakage: When merging lists, modifying references without saving copies will make node references in the middle unreachable.

    7. Summary

  • Three Pointers: prev, curr, nextTemp are needed for in-place reversal.
  • Dummy Node: Ensures merging logic always has a valid previous pointer to link.
  • Complexity: Reversal is O(N) time / O(1) space; merging is O(N + M) time / O(1) space.

    • 8. Quiz

    Question 1: What is the space complexity of reversing a linked list recursively? Answer: O(N) space due to recursion stack frames. If the list is very large, this can trigger a StackOverflow error. The iterative approach is preferred because it runs in O(1) space.
    Question 2: In merging two sorted lists, what is the purpose of the dummy node? Answer: It acts as a placeholder for the head of the merged list. This allows us to append elements to curr.next without checking if the merged list is empty.
    Question 3: How does a Min-Heap help when merging K sorted lists? Answer: A Min-Heap allows us to retrieve the smallest node among the K current heads in O(log K) time. Inserting its successor back into the heap also takes O(log K), allowing us to merge all N total elements in O(N log K) time.
    Question 4: What is the final value of the curr pointer after reversing a linked list? Answer: null. The loop ends when curr == null, and the new head reference is stored in prev.
    Question 5: True or False: Merging two sorted linked lists in-place requires allocating new nodes in memory. Answer: False. We can merge them in-place in O(1) auxiliary space by simply updating the existing node pointers to interleave them.