Merge Two Sorted Lists: 6 Best Tips to Solve It Easily

Merge Two Sorted Lists is Day 19 of the Tekraze DSA series, and it keeps us working with pointers right after yesterday’s in-place flip. You get two lists that are already sorted, and you join them into one sorted list without creating new nodes.

Also Read: Missed yesterday? Day 18 covers Reverse Linked List, the pointer warm-up that makes today much easier.

What is the Merge Two Sorted Lists problem?

You are given the heads of two sorted singly linked lists, list1 and list2. Splice their nodes together into one sorted list and return its head. This is the same task as LeetCode 21, so you can test your own version there after reading this post.

Input:  list1 = 1 -> 2 -> 4, list2 = 1 -> 3 -> 4
Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4

Input:  list1 = empty, list2 = 0
Output: 0

Input:  list1 = empty, list2 = empty
Output: empty list

How should you think about it in plain words?

To solve Merge Two Sorted Lists in plain words, picture two queues of people already lined up by height. To build one line, you keep looking at the front person of each queue and wave the shorter one forward.

When one queue runs out, everyone left in the other queue simply walks in behind. They are already in order, so there is nothing left to compare.

What does the brute force approach look like?

The brute force answer to Merge Two Sorted Lists is to copy every value from both lists into one array, sort it, then build a fresh linked list from the sorted values.

def merge_two_lists_brute(list1, list2):
    vals = []
    for head in (list1, list2):
        while head:
            vals.append(head.val)
            head = head.next
    dummy = tail = ListNode()
    for v in sorted(vals):
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next

It works, but sorting costs O((n + m) log(n + m)) time and you use O(n + m) extra memory. It also throws away the fact that both lists were sorted to begin with, and that fact is the whole hint.

How do we get the optimal Merge Two Sorted Lists solution?

Create a dummy node and keep a tail pointer on it. While both lists still have nodes, compare their heads, attach the smaller one to tail.next, and move that list forward. Then move tail forward too.

When one list is empty, attach whatever is left of the other one in a single step. The answer is dummy.next.

The Merge Two Sorted Lists solution runs in O(n + m) time because every node is looked at once, and it needs only O(1) extra space because we only relink existing nodes. A recursive version reads nicely, but it uses O(n + m) call stack space. For a quick refresher on these bounds, see our Big O helper post on time and space complexity.

Merge Two Sorted Lists in Java

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                tail.next = list1;
                list1 = list1.next;
            } else {
                tail.next = list2;
                list2 = list2.next;
            }
            tail = tail.next;
        }
        tail.next = (list1 != null) ? list1 : list2;
        return dummy.next;
    }
    static ListNode build(int[] vals) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        for (int v : vals) {
            tail.next = new ListNode(v);
            tail = tail.next;
        }
        return dummy.next;
    }
    static String str(ListNode head) {
        StringBuilder sb = new StringBuilder("[");
        for (ListNode c = head; c != null; c = c.next) {
            sb.append(c.val);
            if (c.next != null) sb.append(",");
        }
        return sb.append("]").toString();
    }
    static void check(int[] a, int[] b, String expected) {
        String got = str(new Solution().mergeTwoLists(build(a), build(b)));
        if (!got.equals(expected)) throw new AssertionError("Got " + got + " want " + expected);
    }
    public static void main(String[] args) {
        check(new int[]{1, 2, 4}, new int[]{1, 3, 4}, "[1,1,2,3,4,4]");
        check(new int[]{}, new int[]{}, "[]");
        check(new int[]{}, new int[]{0}, "[0]");
        check(new int[]{5}, new int[]{1, 2, 3}, "[1,2,3,5]");
        check(new int[]{-3, 0, 7}, new int[]{-5, 8}, "[-5,-3,0,7,8]");
        check(new int[]{2, 2}, new int[]{2}, "[2,2,2]");
        System.out.println("All Java tests passed");
    }
}

Merge Two Sorted Lists in Python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
def merge_two_lists(list1: ListNode | None, list2: ListNode | None) -> ListNode | None:
    dummy = ListNode()
    tail = dummy
    while list1 and list2:
        if list1.val <= list2.val:
            tail.next, list1 = list1, list1.next
        else:
            tail.next, list2 = list2, list2.next
        tail = tail.next
    tail.next = list1 or list2
    return dummy.next
def build(vals):
    dummy = ListNode()
    tail = dummy
    for v in vals:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next
def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out
if __name__ == "__main__":
    cases = [
        ([1, 2, 4], [1, 3, 4], [1, 1, 2, 3, 4, 4]),
        ([], [], []),
        ([], [0], [0]),
        ([5], [1, 2, 3], [1, 2, 3, 5]),
        ([-3, 0, 7], [-5, 8], [-5, -3, 0, 7, 8]),
        ([2, 2], [2], [2, 2, 2]),
    ]
    for a, b, expected in cases:
        assert to_list(merge_two_lists(build(a), build(b))) == expected
    print("All Python tests passed")

Merge Two Sorted Lists in Rust

#[derive(Debug, PartialEq, Eq)]
struct ListNode {
    val: i32,
    next: Option<Box<ListNode>>,
}
impl ListNode {
    fn new(val: i32) -> Self {
        ListNode { val, next: None }
    }
}
fn merge_two_lists(
    mut list1: Option<Box<ListNode>>,
    mut list2: Option<Box<ListNode>>,
) -> Option<Box<ListNode>> {
    let mut dummy = Box::new(ListNode::new(0));
    let mut tail = &mut dummy;
    while list1.is_some() && list2.is_some() {
        let take_first = list1.as_ref().unwrap().val <= list2.as_ref().unwrap().val;
        let source = if take_first { &mut list1 } else { &mut list2 };
        let mut node = source.take().unwrap();
        *source = node.next.take();
        tail.next = Some(node);
        tail = tail.next.as_mut().unwrap();
    }
    tail.next = if list1.is_some() { list1 } else { list2 };
    dummy.next
}
fn build(vals: &[i32]) -> Option<Box<ListNode>> {
    let mut head = None;
    for &v in vals.iter().rev() {
        let mut node = Box::new(ListNode::new(v));
        node.next = head;
        head = Some(node);
    }
    head
}
fn to_vec(mut head: Option<Box<ListNode>>) -> Vec<i32> {
    let mut out = Vec::new();
    while let Some(node) = head {
        out.push(node.val);
        head = node.next;
    }
    out
}
fn check(a: &[i32], b: &[i32], expected: &[i32]) {
    assert_eq!(to_vec(merge_two_lists(build(a), build(b))), expected);
}
fn main() {
    check(&[1, 2, 4], &[1, 3, 4], &[1, 1, 2, 3, 4, 4]);
    check(&[], &[], &[]);
    check(&[], &[0], &[0]);
    check(&[5], &[1, 2, 3], &[1, 2, 3, 5]);
    check(&[-3, 0, 7], &[-5, 8], &[-5, -3, 0, 7, 8]);
    check(&[2, 2], &[2], &[2, 2, 2]);
    println!("All Rust tests passed");
}

All three Merge Two Sorted Lists programs ran the classic 1, 2, 4 and 1, 3, 4 example, two empty lists, one empty list, lists of very different lengths, negative numbers, and repeated values. Every check passed in Java, Python and Rust.

What are the 6 best tips for an easy Merge Two Sorted Lists solution?

1. Spot the pattern. Two sorted inputs and one sorted output almost always means a two-pointer merge, the same step that sits inside merge sort.
2. Use a dummy head. It removes the special case of choosing the first node, so the loop body stays the same every time.
3. Attach the leftover in one line. When one list ends, the other is already sorted, so point tail.next at it and stop.
4. Use less than or equal. Taking from the first list on ties keeps the merge stable, which matters when nodes carry extra data.
5. Use take() in Rust. The Option::take method moves a node out of an Option, so you never fight the borrow checker over the tail pointer.
6. Say the brute force first in interviews. Then point out that sorted input lets you skip sorting. Mention that the same idea scales to Merge k Sorted Lists with a heap.

What are the common Merge Two Sorted Lists mistakes?

• Forgetting to move tail forward after attaching a node, so every node overwrites the last one.
• Looping until both lists are empty and then reading a null head.
• Returning dummy instead of dummy.next.
• Building brand new nodes when the problem asks you to splice the existing ones.
• Not handling an empty input, which should just return the other list.

Where is the Merge Two Sorted Lists pattern used in the real world?

The merge step shows up everywhere sorted data meets. Databases use it in merge joins, and the PostgreSQL planner documentation describes how a merge join walks two sorted inputs side by side.

Log tools use the same idea to combine time-ordered log files from several servers. External sorting merges sorted chunks that did not fit in memory, and search engines merge sorted lists of document ids when they combine results.

Which earlier posts in the series should you read?

Start with Day 1, Two Sum for hash map basics and Day 2, Best Time to Buy and Sell Stock for tracking a running minimum. Day 3, Contains Duplicate, Day 4, Valid Anagram and Day 5, Group Anagrams build the counting toolkit.

Day 6, Valid Palindrome, Day 7, Two Sum II, Day 8, 3Sum and Day 9, Container With Most Water cover two pointers. Day 10, Longest Substring Without Repeating Characters, Day 11, Longest Repeating Character Replacement and Day 12, Minimum Window Substring walk through the sliding window section.

Day 13, Valid Parentheses, Day 14, Min Stack, Day 15, Evaluate Reverse Polish Notation and Day 16, Daily Temperatures cover the stack chapter. Day 17, Implement Queue using Stacks opens queues, and Day 18, Reverse Linked List starts the linked list chapter. You can follow every day in order on the DSA series hub.

Keep our data structures cheat sheet handy for a quick look at how linked lists compare with arrays, stacks and queues.

Conclusion

Merge Two Sorted Lists comes down to one habit: compare the two front nodes, attach the smaller one, and move on. Use a dummy head, always advance tail, and attach the leftover list in one step. Tomorrow we keep working through the linked list chapter, so run all three solutions once before you move on.

Frequently asked questions about Merge Two Sorted Lists

What is the Merge Two Sorted Lists problem?

You get the heads of two sorted linked lists and splice their nodes into one sorted list, then return its head.

Why use a dummy node when merging linked lists?

A dummy node gives you a fixed starting point, so you never need a special case for picking the first node of the result.

What is the time and space complexity of merging two sorted lists?

The iterative merge runs in O(n + m) time and O(1) extra space. The recursive version is also O(n + m) time but uses O(n + m) stack space.

What happens when one list is longer than the other?

Once the shorter list runs out, the rest of the longer list is already sorted, so you attach it to the tail in one step.

How does Merge Two Sorted Lists relate to merge sort?

It is exactly the merge step of merge sort, and the same idea extends to merging k sorted lists with a min heap.