4일차 - 두 개의 정렬된 목록 병합

문제

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.

예 1:

Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]

예 2:

Input: l1 = [], l2 = []
Output: []

예 3:

Input: l1 = [], l2 = [0]
Output: [0]

내 테스트

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

내 솔루션

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

분석

내 해설

나는 이것을 내 머리에서하는 것과 거의 정확하게 코드로했습니다. 다시 말하지만, 그것은 상당히 쓰레기 솔루션이지만 시간이 다되었습니다. 나는 이것들을 더 빨리 하기 위해 열심히 노력하고 있지만 까다롭다는 것을 알게 되었습니다.

2개의 목록을 볼 때 병합된 목록을 수동으로 만들려면 두 목록 중 가장 낮은 번호부터 시작하여 병합된 목록에 추가할 가능성이 높습니다. 이 작업도 제자리에서 수행할 수 있지만 이를 새 목록에 넣는다고 가정해 보겠습니다. 그런 다음 두 목록 중 하나에서 순서대로 다음 번호를 찾아 추가하는 식입니다. 처음에 가장 작은 숫자가 있는 목록을 출력 목록으로 사용하는 것을 제외하고는 그렇게 코딩했습니다.

나는 이것으로 올바른 길을 가고 있다고 생각하지만 코드를 약간 정리해야 합니다. 상당히 지저분합니다.