EasyLinked ListRecursion

Merge Two Sorted Lists

1 approach, code in every language

You are given the heads of two linked lists that are each sorted in non-decreasing order. Combine them into a single sorted list.

The merged list should be built by splicing together the existing nodes of the two inputs rather than by allocating new ones. Return the head of the resulting list.

Example 1

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

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

Repeatedly picking the smaller front node from the two lists interleaves them into a single sorted chain.

Example 2

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

Output: [0]

When one list is empty there is nothing to compare, so the answer is simply the other list.

Constraints

The number of nodes in both lists is in the range [0, 50].
-100 <= Node.val <= 100
Both list1 and list2 are sorted in non-decreasing order.

Dummy Head with Tail Splicing

Grow the answer behind a dummy head, always attaching the smaller of the two current nodes.

Loading animation…

Intuition

Because both inputs are already sorted, the next node in the merged output is always whichever front node is smaller. That observation turns the problem into a simple linear scan with two pointers. A dummy head removes the awkwardness of choosing and initializing the very first node: we just keep a tail pointer and splice nodes onto it. Each comparison advances exactly one input pointer, so no nodes are ever revisited. When one list runs out, everything remaining in the other list is already sorted and larger, so we attach it wholesale.

Algorithm walkthrough

1Create a dummy node and a tail pointer that starts at the dummy.
2While both lists still have nodes, compare their head values.
3Attach the node with the smaller value to tail.next and advance that list's pointer.
4Advance the tail pointer to the node just attached.
5Once the loop ends, at most one list is non-empty; attach it directly to tail.next.
6Return dummy.next as the head of the merged list.

Implementation

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        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

Time

O(m + n)

Space

O(1)

We visit each node from both lists at most once and rewire pointers in place, so no extra list storage is needed beyond the dummy header.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Linked List

After the pattern

Now solve one you haven't seen.

Splice Index Card Chains is our own problem on the technique behind Merge Two Sorted Lists: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free