Skip to content

21. Merge Two Sorted ListsΒΆ

Problem Link

To solve this in a single pass, we can use a dummy node along with a pointer curr. At each step, we compare the current nodes of both lists and link the smaller one to curr.

After linking, we advance the pointer in the list from which the node was taken, and move curr forward. Once one list is exhausted, we directly link the remaining nodes of the other list, since they are already sorted.

Runtime Complexity

Time: \(O(n)\)

Space: \(O(1)\)

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

        if list1:
            curr.next = list1
        if list2:
            curr.next = list2
        return dummy.next

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    dummy := &ListNode{Val: 0, Next: nil}
    curr := dummy
    for list1 != nil && list2 != nil {
        if list1.Val <= list2.Val {
            curr.Next = list1
            list1 = list1.Next
        } else {
            curr.Next = list2
            list2 = list2.Next
        }
        curr = curr.Next
    }
    if list1 != nil {
        curr.Next = list1
    } else if list2 != nil {
        curr.Next = list2
    }
    return dummy.Next
}