DEV Community

loading...

Day 4 - Merge Two Sorted Lists

ruarfff profile image Ruairí O'Brien ・2 min read

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:

Alt Text

Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]
Enter fullscreen mode Exit fullscreen mode

Example 2:

Input: l1 = [], l2 = []
Output: []
Enter fullscreen mode Exit fullscreen mode

Example 3:

Input: l1 = [], l2 = [0]
Output: [0]
Enter fullscreen mode Exit fullscreen mode

My Tests

Link to util code

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

Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Analysis

Alt Text

Alt Text

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.

Discussion (0)

pic
Editor guide