Leetcode - 21. Merge Two Sorted Lists

Easy

Dec 22, 2025

#linked-list

21. Merge Two Sorted Lists

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

Merge the two lists into 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.

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]

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.

Constraints:

Notes

Intuition

Since both lists are sorted, we can build the merged list by always taking the smaller of the two current nodes. This is similar to the merge step in merge sort.

Implementation

Create a dummy node to simplify head handling and a curr pointer for building the result. While both lists have nodes, compare their values—append the smaller one to the result and advance that list's pointer. After the main loop, one list may have remaining nodes; append them directly since they're already sorted.

Edge-cases

If either list is initially empty, the other list is returned as-is. The dummy node eliminates special case handling for the first element.

Time: O(m + n) — each node visited once
Space: O(1) — reusing existing nodes (or O(m + n) if creating new nodes)

Complexity

Solution

from typing import Optional
from lcutils import ListNode

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        l1, l2 = list1, list2
        dummy = ListNode()
        curr = dummy
        while l1 and l2:
            if l1.val < l2.val:
                curr.next = ListNode(l1.val)
                l1 = l1.next
            else:
                curr.next = ListNode(l2.val)
                l2 = l2.next
            curr = curr.next

        while l1:
            curr.next = ListNode(l1.val)
            curr = curr.next
            l1 = l1.next

        while l2:
            curr.next = ListNode(l2.val)
            curr = curr.next
            l2 = l2.next

        return dummy.next
        



if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()