< Back




21. Merge Two Sorted Lists

We're given two sorted linked lists where each node has an integer value. We're asked to merge the
two linked lists, maintaining their sorted property, and return the head. Pretty straightforward, we
traverse both linked lists simultaneously comparing their values. We maintain a dummy node to keep
track of the new head, and we maintain a head to add nodes to the merged linked list.

If the value in list1 is less than the value in list2, we append it to the list, else we append the
value from list2 to the list. Finally, we check to make sure no nodes remain in list1 and list2. If
nodes remain, we append them.

Then we return dummy.next, which is the head node of the new merged linked list.

The solution is as follows:


  class Solution:
      def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
          dummy = ListNode()
          head = dummy

          while list1 and list2:
              if list1.val < list2.val:
                  head.next, list1 = list1, list1.next
              else:
                  head.next, list2 = list2, list2.next

              head = head.next

          while list1:
              head.next, list1 = list1, list1.next
              head = head.next

          while list2:
              head.next, list2 = list2, list2.next
              head = head.next

          return dummy.next


_ Time Complexity:

  O(n + m) - We traverse all nodes within lists 1 and 2.

_ Space Complexity:

  O(1) - We maintain a dummy node to keep track of the head of the new linked list.