LeetEye LeetEye
Medium Linked List ~5 min

Merge Two Sorted Lists

linked-list merge-two-sorted-lists

Problem

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Examples

Example 1
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Example 2
Input: list1 = [], list2 = []
Output: []
Example 3
Input: list1 = [], list2 = [0]
Output: [0]
Key Insight

Compare heads of both lists. Take the smaller one, advance that list's pointer. Repeat.

Compare heads, take smaller, advance that pointer. Use dummy node. Attach remaining list when one exhausts.

How to Approach This Problem

Pattern Recognition: When you see keywords like merge two sorted lists linked-list, think Linked List.

Step-by-Step Reasoning

1 At each step, we compare:
Answer: Heads (current nodes) of both lists
Both lists are sorted. Smallest remaining element is always at the head of one list.
2 If list1.val < list2.val, we:
Answer: Take node from list1
We want sorted order. Smaller goes first.
3 After appending a node from list1, we:
Answer: Advance list1 to list1.next
We've used this node. Move to the next candidate.
4 A dummy node helps because:
Answer: It simplifies handling the head of result
Without dummy, we need special logic for the first node. With dummy, we always append to dummy's current position.
5 When list1 becomes null (exhausted):
Answer: Append remaining list2
Remaining nodes of list2 are already sorted. Just attach them.
6 We return:
Answer: dummy.next
Dummy is just a placeholder. The actual merged list starts at dummy.next.

Solution

def mergeTwoLists(list1: ListNode, list2: ListNode) -> ListNode:
    dummy = ListNode()
    curr = dummy
    
    while list1 and list2:
        if list1.val <= list2.val:
            curr.next = list1
            list1 = list1.next
        else:
            curr.next = list2
            list2 = list2.next
        curr = curr.next
    
    # Attach remaining nodes
    curr.next = list1 if list1 else list2
    
    return dummy.next

Complexity Analysis

Time O(n + m)
Space O(1)

Master This Pattern

Build intuition with interactive MCQs. Practice Linked List problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye