## DEV Community is a community of 871,761 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Day 4 - Merge Two Sorted Lists

## 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 = 
Output: 
``````

## 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],
),
([], , ),
([], [], []),
],
)
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.