LC21. Merge Two Sorted Lists

Approach 1: Optimal

# 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]:
        head3 = curr = ListNode(0, None)
 
        while list1 is not None and list2 is not None:
            if list1.val <= list2.val:
                curr.next = list1
                list1 = list1.next
            else:
                curr.next = list2
                list2 = list2.next
            
            curr = curr.next
        
        if list1 is not None:
            curr.next = list1
        
        if list2 is not None:
            curr.next = list2
        
        return head3.next

Complexity

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

Notes

It’s better to use a dummy head node in this case which simplifies the logic. Approaching with a null head will add more code complexity.

Other Languages

Go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    curr := &ListNode{}
    head3 := curr
 
    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
    }
 
    if list2 != nil {
        curr.Next = list2
    }
 
    return head3.Next
}