LeetCode · #21

Merge Two Sorted Lists Solution

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

Section One · Problem

Problem Statement

🏷️

Difficulty

Easy

🔗

LeetCode

Problem #21

🏗️

Pattern

Merge — dummy head technique

Given the heads of two sorted linked lists list1 and list2, merge them into one sorted list made by splicing together the nodes of the two lists. Return the head of the merged list.

Example

 Input: list1 = 1→2→4,  list2 = 1→3→4 Output: 1→1→2→3→4→4 

Constraints

 • 0 ≤ list length ≤ 50 • -100 ≤ Node.val ≤ 100 • Both lists are sorted in non-decreasing order 

Section Two · Approach 1

Collect & Sort — O(n log n)

Collect all values into an array, sort, and build a new list. Wastes the fact that both lists are already sorted.

Problem: O(n log n) sorting is unnecessary. A single pass comparing heads of both lists — like merge sort's merge step — gives O(n+m).

Section Three · Approach 2

Iterative Merge — O(n + m)

Create a dummy head node. Compare the current heads of both lists, link the smaller one to the merged list, and advance that pointer. When one list is exhausted, link the remainder of the other.

💡 Mental model: Two sorted stacks of exam papers. Pick up the top paper from whichever stack has the smaller grade number, place it on your merged pile. When one stack runs out, dump the rest of the other stack onto the pile.

Algorithm

Step 1: Create dummy = new ListNode(0), tail = dummy.
Step 2: While both lists non-null: compare values, link smaller to tail, advance that list pointer.
Step 3: Link remaining non-null list to tail.
Step 4: Return dummy.next.

🎯 Dummy head trick:

The dummy node avoids special-casing the first insertion.
Without it, you'd need an if-statement to set the head of the result.
With it, you always link to tail.next and return dummy.next.
This trick appears in most linked-list merge/build problems.

Section Four · Trace

Visual Walkthrough

Trace: list1 = 1→2→4, list2 = 1→3→4:

Iterative merge — compare heads, link smaller

Section Five · Implementation

Code — Java & Python

Java — Iterative Merge

 class Solution {
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;
        }

        tail.next = (l1 != null) ? l1 : l2;
return dummy.next;
    }
}

Python — Iterative Merge

 class Solution:
def mergeTwoLists(self, l1, l2):
        dummy = tail = ListNode(0)
while l1 and l2:
if l1.val <= l2.val:
                tail.next = l1
                l1 = l1.next
else:
                tail.next = l2
                l2 = l2.next
            tail = tail.next

        tail.next = l1 or l2
return dummy.next

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Iterative Merge ← optimal	O(n + m)	O(1)	In-place splicing with dummy head
Recursive	O(n + m)	O(n + m)	Clean code but O(n+m) stack depth

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Both empty	`null, null`	Loop doesn't execute, tail.next = null → return null.
One empty	`null, 1→2`	Loop skips, tail.next = l2 → return l2 directly.
Different lengths	`1→2, 1→2→3→4`	Shorter runs out first, rest linked in one step.

⚠ Common Mistake: Forgetting to advance tail = tail.next after linking. Without it, every new node overwrites the same tail.next, and you only get the last linked node in the result.

← Back to Linked List problems

LearningTree

LC 21 · Merge Two Sorted Lists — Solution & Explanation | DSA Guide