Skip to main content
DSA patterns

Merge Two Sorted Lists

easyLinked list Must-doTCSInfosysAccenture

Problem statement

You are given the heads of two singly linked lists, list1 and list2, and both are already sorted in non-decreasing order. Combine them into a single sorted linked list by reusing the existing nodes — don't create new ones — and return the head of the merged list.

Either list, or both, may be empty.

Examples

Example 1

Input: list1 = [1, 2, 4], list2 = [1, 3, 4]

Output: [1, 1, 2, 3, 4, 4]

Explanation: At each step the smaller of the two current front values is picked next; the two 1s and two 4s both make it in, in the order their lists offered them.

Example 1

Example 2

Input: list1 = [], list2 = []

Output: []

Explanation: Both lists are empty, so there's nothing to merge.

Example 3

Input: list1 = [], list2 = [0]

Output: [0]

Explanation: One list is empty, so the merged list is simply the other list, unchanged.

Hints

Hint 1: You never need to look further than the two nodes currently at the front of each list — the smaller of those two is always the next node in the answer.

Approach

Optimal: Two pointers with a dummy node, iterative

Intuition

Do the same "always take the smaller front node" idea as recursion, but with a loop instead of function calls, so there's no stack to grow. A dummy node placed just before the real answer gives the loop somewhere to attach the very first real node without a special case — you always attach after tail, and tail always exists from the start.

Steps

  1. Create a dummy node and set tail to point at it.
  2. While both list1 and list2 still have nodes, compare their front values.
  3. Attach the smaller one after tail, and move that list's pointer forward past the node just used.
  4. Move tail forward to the node just attached.
  5. When one list runs out, attach whatever remains of the other list directly — it's already sorted.
  6. Return dummy.next (the dummy itself is never part of the answer).

Dry run

list1 = [1, 2, 4], list2 = [1, 3, 4]

step compare attach list1 left list2 left
1 1 vs 1 list1's 1 [2, 4] [1, 3, 4]
2 2 vs 1 list2's 1 [2, 4] [3, 4]
3 2 vs 3 list1's 2 [4] [3, 4]
4 4 vs 3 list2's 3 [4] [4]
5 4 vs 4 list1's 4 [] [4]
6 list1 empty attach rest of list2 [] []

Result: 1 → 1 → 2 → 3 → 4 → 4.

Edge cases: if either list starts empty, the while loop never runs, and the "attach what's left" step immediately returns the other list unchanged.

Complexity

Time O(n+m) - one pass across both lists together; every node is looked at once and attached once.

Space O(1) - extra — beyond the two input lists and one dummy node, nothing new is allocated, and there's no call stack to grow.

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


class Solution:
    def mergeTwoLists(self, list1, list2):
        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 if list1 else list2
        return dummy.next


def build_list(values):
    dummy = ListNode()
    tail = dummy
    for v in values:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next


def to_values(node):
    out = []
    while node:
        out.append(node.val)
        node = node.next
    return out


if __name__ == "__main__":
    print(to_values(Solution().mergeTwoLists(build_list([1, 2, 4]), build_list([1, 3, 4]))))
    print(to_values(Solution().mergeTwoLists(build_list([]), build_list([]))))
    print(to_values(Solution().mergeTwoLists(build_list([]), build_list([0]))))
RecapThe whole problem in a few lines, for the night before
  • Spot it: "combine two already-sorted lists into one sorted list"
  • Idea: always take the smaller of the two current front nodes; a dummy head avoids a special case for the first pick
  • Cost: O(n+m) time; O(1) extra space iteratively (O(n+m) stack recursively)
  • Trap: forgetting to attach the leftover tail of whichever list still has nodes once the other one runs out

Interview follow-ups

  • Merge k sorted linked lists instead of just two.

    Repeatedly calling this two-list merge on the lists one pair at a time works but costs O(k · n) in the worst case. A faster way keeps a min-heap holding the current front node of each of the k lists; repeatedly pop the smallest, attach it to the result, and push that list's next node if it has one. That runs in O(N log k) time for N total nodes, since each of the N pops and pushes costs O(log k).

  • The two lists are too large to hold in memory and arrive as streams (for example, two sorted log files read line by line).

    The same two-pointer idea still works without changing its shape: instead of following next pointers, read one line at a time from each stream, compare, and write out the smaller one, advancing only that stream's reader. Memory stays O(1) regardless of how large the files are, since only the current line of each stream needs to be held at once.

Frequently asked questions

Sorting throws away the fact that both lists already arrive sorted — that's a fact you get for free, and the optimal approach uses it directly, dropping the cost from O((n+m) log(n+m)) down to O(n+m).

Without it, you'd need an if-check just for the very first node — is the result's head list1's first node or list2's? A dummy node sidesteps that entirely: you always attach after tail, and at the end dummy.next is whatever the first real node turned out to be.

Merging is the core of combining sorted log streams from different hosts by timestamp, or merging sorted shard outputs back into one ordered result — the same "always take the smaller current front item" logic, just applied to log lines or records instead of linked-list nodes.

The problem only requires the merged list to be non-decreasing, so either order is a valid answer for equal values. This solution's <= comparison happens to prefer list1's node on a tie, which is a natural and stable choice, but the checker doesn't require it.