Merge Two Sorted Lists in Python

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:

Input: 1 -> 2 -> 4, 1 -> 3 -> 4
Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4

Approach

We get 2 linked lists. l1 and l2 we can consider as the head of their own lists. There are many approaches to this but in this blog we are going to create a new list node and return that. We go through our 2 linked lists and compare the heads. Our new list node will then reference the lower node of the 2. If they are both the same it doesn't matter which one we reference. Once we finish a list we will just reference the rest of the other list. We know a list is finished once it hits None value. Couple things we have to be aware of is:

1. We are using a dummy variabe to create our new list node
2. We need to keep track of the head, which is why we create 2 list nodes
3. We need to move l1 and l2 pointers (heads) accordingly
4. We have to move our dummy pointer everytime we reference a node

Solution

# 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, l1: ListNode, l2: ListNode) -> ListNode:
        # We create a new linked list with dummy being the head.
        # 0 is just a val i assign, anything < 1 is fine
        dummy = ListNode(0)
        head = dummy

        # While niether list has reached the end
        while l1 != None and l2 != None:
          # we compare the pointers to see which one is lower
          if l1.val < l2.val:
            # dummy node points to the next node, which this case is l1
            dummy.next = l1
            # move the pointer at l1 forward
            l1 = l1.next
          else:
            dummy.next = l2
            l2 = l2.next
          # reassign dummy pointer to keep up with the newly referenced nodes
          dummy = dummy.next
        # When one list reaches the end
        if l1 == None:
          # Add the rest of the nodes from l2
          # This works becasue each node has a reference to it's next node
          dummy.next = l2
        else:
          dummy.next = l1
        # we don't want to return None or our default val. Return val after none
        return head.next

One thing to note about linked lists is that a head and a linked list is synonymous

We are not creating any new nodes besides our dummy node and head node. Everything I do below is just referencing (AKA node pointing to another node).

 

Step by Step Example

# l1: 1 -> 2 -> 4 -> None
# l2: 1 -> 3 -> 4 -> None
# dummy: 0
         ^

1st iteration

# l1: 1 -> 2 -> 4 -> None
      ^
# l2: 1 -> 3 -> 4 -> None
           ^
# dummy: 0 -> 1
              ^

2nd iteration

# l1: 1 -> 2 -> 4 -> None
           ^
# l2: 1 -> 3 -> 4 -> None
           ^
# dummy: 0 -> 1 -> 1
                   ^

3rd iteration

# l1: 1 -> 2 -> 4 -> None
                ^
# l2: 1 -> 3 -> 4 -> None
           ^
# dummy: 0 -> 1 -> 1 -> 2
                        ^

4th iteration

# l1: 1 -> 2 -> 4 -> None
                ^
# l2: 1 -> 3 -> 4 -> None
                ^
# dummy: 0 -> 1 -> 1 -> 2 -> 3
                             ^

5th iteration

# l1: 1 -> 2 -> 4 -> None
                ^
# l2: 1 -> 3 -> 4 -> None
                      ^
# dummy: 0 -> 1 -> 1 -> 2 -> 3 -> 4
                                  ^

break out of while loop

# l1: 1 -> 2 -> 4 -> None
                ^
# l2: 1 -> 3 -> 4 -> None
                      ^
# dummy: 0 -> 1 -> 1 -> 2 -> 3 -> 4 -> 4
                                  ^

• If there were more nodes after the second 4 you would get references to those nodes becasue the second 4 is going to point to another node.

Return the head which is first 1

return head.next

Let me know how you liked the blog. If anything is wrong please feel free to comment below or message me directly.

Problem on Leetcode

Video solution in Java by Kevin Naughton Jr.