The Problem
Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.
Example 1:
Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]
Example 2:
Input: l1 = [], l2 = []
Output: []
Example 3:
Input: l1 = [], l2 = [0]
Output: [0]
My Tests
import pytest
from typing import List
from .util import ListNode, toListNode, toList
from .Day4 import Solution
s = Solution()
@pytest.mark.parametrize(
"l1,l2,expected",
[
([1, 2, 4], [1, 3, 4], [1, 1, 2, 3, 4, 4]),
([1, 9, 22], [-3, 4, 30], [-3, 1, 4, 9, 22, 30]),
(
[-3, 4, 31, 49],
[-20, -20, -3, 1, 4, 9, 22, 40, 40],
[-20, -20, -3, -3, 1, 4, 4, 9, 22, 31, 40, 40, 49],
),
([], [0], [0]),
([], [], []),
],
)
def test_merge_sorted_list(l1, l2, expected):
list_root1 = toListNode(l1)
list_root2 = toListNode(l2)
assert toList(s.mergeTwoLists(list_root1, list_root2)) == expected
My Solution
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if l1 is None:
return l2
if l2 is None:
return l1
out = None
l_next = None
if l1.val > l2.val:
out = l2
l_next = l1
else:
out = l1
l_next = l2
out_next = out
while l_next is not None:
if out_next.next is None:
out_next.next = l_next
l_next = None
elif l_next.val >= out_next.val and l_next.val <= out_next.next.val:
new_node = ListNode(l_next.val, out_next.next)
out_next.next = new_node
l_next = l_next.next
out_next = out_next.next
return out
Analysis
My Commentary
I did this one in code pretty much exactly how I would do it in my head. Again, it's a fairly crap solution but time ran out. I am trying hard to get faster at these but finding it tricky.
When you look at the 2 lists, if you manually were to create a merged list, likely you would start with the lowest number from either list and add it to the merged list. You might do this in place too but let's say we're putting this in a new list. You would then look for the next number in sequence from either list and add that and so on. I coded it up that way except used the list with the smallest number at the start as the output list.
I think I was more or less on the right path with this one but need to clean up the code a bit. It's quite messy.
Top comments (0)