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.
Input: 1 -> 2 -> 4, 1 -> 3 -> 4 Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4
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:
- We are using a dummy variabe to create our new list node
- We need to keep track of the head, which is why we create 2 list nodes
- We need to move l1 and l2 pointers (heads) accordingly
- We have to move our dummy pointer everytime we reference a node
# 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).
# l1: 1 -> 2 -> 4 -> None # l2: 1 -> 3 -> 4 -> None # dummy: 0 ^
# l1: 1 -> 2 -> 4 -> None ^ # l2: 1 -> 3 -> 4 -> None ^ # dummy: 0 -> 1 ^
# l1: 1 -> 2 -> 4 -> None ^ # l2: 1 -> 3 -> 4 -> None ^ # dummy: 0 -> 1 -> 1 ^
# l1: 1 -> 2 -> 4 -> None ^ # l2: 1 -> 3 -> 4 -> None ^ # dummy: 0 -> 1 -> 1 -> 2 ^
# l1: 1 -> 2 -> 4 -> None ^ # l2: 1 -> 3 -> 4 -> None ^ # dummy: 0 -> 1 -> 1 -> 2 -> 3 ^
# 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
Let me know how you liked the blog. If anything is wrong please feel free to comment below or message me directly.