21. Merge Two Sorted Lists

Problem Statement

link: LeetCode.cn LeetCode 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:

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

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

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

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.

Solution Approach

Iteratively compare nodes from both lists, attaching the smaller node to a new dummy list, and finally append any remaining nodes.

Algorithm

1. Iterative Comparison: Compare the values of nodes from both lists, appending the smaller node to the merged list and advancing the corresponding list pointer.
2. Dummy Node: Use a dummy node to simplify list operations and facilitate easy attachment of nodes from the two lists.
3. Handle Remaining Nodes: After one of the lists is exhausted, directly attach the remaining nodes of the other list to the end of the merged list.

Implement

    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]:
        #dummy
        #iterate two lists : check the smaller value and append to dummy list
        # append remain list1 or 2
        dummy = ListNode(0)
        res = dummy
        while list1 and list2:
            if list1.val < list2.val:
                dummy.next = list1
                list1 = list1.next
            else:
                dummy.next = list2
                list2 = list2.next
            dummy = dummy.next
        dummy.next = list1 if list1 is not None else list2
        return res.next
    

    
    

Twitter  facebook  Email