You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists in a 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.
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Input: list1 = [], list2 = []
Output: []
Input: list1 = [], list2 = [0]
Output: [0]
Definition for singly-linked list:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
Solution
The original nodes have to be used. The "output list" is initially empty, so we can create a dummy node that points to the output list initially.
The dummy node will be initialized to list1 first, and we can start comparing the subsequent values:
Input: list1 = [1,2,4], list2 = [1,3,4]
dummy = node 1
# compare 1 (from list2) and 2 (from list1)
# insert node 1 (from list2) to end
When there are no more values in a list, simply add the nodes to the end of the output list (the provided lists are already sorted).
Python
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
# Pointer to beginning of output
dummy = ListNode()
tail = dummy
# We can compare values when BOTH lists still have a node
while list1 and list2:
# Insert smaller value to tail
if list1.val < list2.val:
tail.next = list1
list1 = list1.next
else:
tail.next = list2
list2 = list2.next
tail = tail.next
# Check if a list is not empty
if list1:
tail.next = list1
elif list2:
tail.next = list2
# return.next because dummy is just a pointer to the output
return dummy.next