Merge Two Sorted Lists easy

Problem Statement

Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.

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]

Steps

  1. Handle Empty Lists: Check if either list1 or list2 is empty. If so, return the non-empty list or an empty list if both are empty.

  2. Initialize Dummy Node: Create a dummy node (a node with value 0) to simplify the process of handling the head of the merged list. We'll use this dummy node to build the new list, making it easier to handle edge cases.

  3. Initialize Pointers: Create pointers tail (initially pointing to the dummy node) and p1 (pointing to the head of list1), and p2 (pointing to the head of list2).

  4. Iterative Comparison and Merging: Iterate while both p1 and p2 are not None. Compare the values at p1 and p2.

    • If p1.val <= p2.val, append p1 to the tail and move p1 to the next node.
    • Otherwise, append p2 to the tail and move p2 to the next node.

  5. Handle Remaining Nodes: After one list is exhausted, append the remaining nodes from the other list to the tail.

  6. Return Merged List: Return the next node after the dummy node (which is the head of the merged sorted list).

Explanation

The algorithm uses a simple iterative approach to merge the two sorted lists. By using a dummy node, we avoid special handling of the head of the merged list, making the code cleaner and easier to understand. The comparison in the loop ensures that the nodes are added to the merged list in sorted order. The handling of remaining nodes after one list is exhausted ensures that all nodes are included in the result.

Code

# 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: ListNode, list2: ListNode) -> ListNode:
        dummy = ListNode()  # Dummy node
        tail = dummy
        
        while list1 and list2:
            if list1.val <= list2.val:
                tail.next = list1
                list1 = list1.next
            else:
                tail.next = list2
                list2 = list2.next
            tail = tail.next
            
        tail.next = list1 or list2  # Append remaining nodes
        
        return dummy.next

Complexity

  • Time Complexity: O(m + n), where 'm' and 'n' are the lengths of list1 and list2 respectively. We iterate through each list once.
  • Space Complexity: O(1). We use a constant amount of extra space to store pointers. The space used by the linked lists themselves is not considered in the space complexity analysis.