Coding interview problems › Linked Lists

🔗 Linked Lists Easy

Merge Two Sorted Lists

Merge two sorted linked lists by splicing nodes behind a dummy head, always taking the smaller front node. Tested Python, recursion note, pitfalls, live visual.

Also searched as: merge two sorted linked lists · merge sorted lists with dummy node · merge step of merge sort

🔗

Try it live Free

Linked Lists: Reverse & Floyd's Cycle

Practise moving pointers safely in the linked list lab's reverse mode; merging uses the same discipline, re-pointing one next link per step without losing the rest of a list.

Also useful: Sorting Race: Insertion vs Merge vs Quick

Open the playground →

The problem

Given the heads of two linked lists that are each sorted in non-decreasing order, splice their nodes together into one sorted list and return its head. Reuse the existing nodes rather than creating new ones.

Input1 -> 3 -> 5 and 2 -> 3 -> 6
Output1 -> 2 -> 3 -> 3 -> 5 -> 6
Inputempty and 0
Output0

The key insight

The smallest remaining value is always at the front of one of the two lists. Repeatedly detach the smaller front node and attach it to the tail of the result. A dummy node in front of the result means you never need a special case for the very first node.

Brute force first: Copy all values into a Python list, sort it and build a new linked list: O((m + n) log(m + n)) time and extra nodes, ignoring that both lists are already sorted.

Step-by-step approach

  1. Create a dummy node and a tail pointer at it.
  2. While both lists are non-empty, compare their front values.
  3. Attach the smaller front node to tail.next, advance that list, then advance tail.
  4. When one list runs out, attach the remainder of the other list in one step.
  5. Return dummy.next.

Python solution

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


def merge_two_lists(a, b):
    dummy = tail = ListNode()
    while a and b:
        if a.val <= b.val:          # <= keeps equal values stable
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b              # one list is empty; attach the rest
    return dummy.next

Complexity

TimeO(m + n)
SpaceO(1)

Each node is attached exactly once, and no new nodes are created apart from the dummy. A recursive solution also takes O(m + n) time but O(m + n) stack space.

Common mistakes

Frequently asked questions

What is the time and space complexity?

O(m + n) time where m and n are the list lengths, and O(1) extra space for the iterative version.

Can I solve it recursively?

Yes: return the smaller head after setting its next to the merge of its next with the other list. It is short, but uses O(m + n) call-stack depth, which can overflow for very long lists.

How does this extend to k sorted lists?

Merging pairs repeatedly or using a min-heap of the current heads gives O(N log k) for N total nodes. See Merge K Sorted Lists.

Why use a dummy node?

It gives the result list a fixed starting point, so the first attachment works exactly like every other one and you avoid an extra if for an empty result.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Linked Lists Linked Lists: Reverse & Floyd's Cycle lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.