LeetCode-21 Merge Two Sorted Lists

21. Merge Two Sorted Lists  Easy

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]

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.

Solutions:

class Solution(object):
    # This function merges two sorted linked lists into a single sorted linked list.
    # It takes two non-reduced sequences 'list1' and 'list2' as input.
    def mergeTwoLists(self, list1, list2):
        # Initialize a new ListNode as the head of the merged list
        head = ListNode()
        # Initialize a pointer 'current' to traverse the merged list
        current = head
        
        # Continue until either list1 or list2 becomes None
        while list1 and list2:
            # If the value of the current node in list1 is smaller than list2
            if list1.val < list2.val:
                # Append the current node of list1 to the merged list
                current.next = list1
                # Move to the next node in list1
                list1 = list1.next
            else:
                # Append the current node of list2 to the merged list
                current.next = list2
                # Move to the next node in list2
                list2 = list2.next
            # Move the 'current' pointer to the last appended node
            current = current.next
        
        # Connect the remaining nodes of list1 or list2 to the merged list
        current.next = list1 or list2
        
        # Return the head of the merged list (excluding the dummy node)
        return head.next