What is the best way to solve Merge Two Sorted Lists?

The optimized O(n) approach using Linked List patterns is generally preferred.

상위 150개 인터뷰쉬움

두 개의 정렬된 목록 병합

'두 개의 정렬된 목록 병합' 문제에 대한 자세한 가이드 및 Python 구현입니다.

문제 설명

쉬움

두 개의 정렬된 연결 목록 list1과 list2의 헤드가 제공됩니다. 두 목록을 하나의 정렬된 목록으로 병합합니다. 목록은 처음 두 목록의 노드를 함께 연결하여 만들어야 합니다. 병합된 연결 목록의 헤드를 반환합니다.

연결된 목록은 Python 목록으로 표시됩니다. 병합된 정렬 목록을 반환하는 mergeTwoLists(list1: list, list2: list) -> list 함수를 구현하세요.

제약

•The number of nodes in both lists is in the range [0, 50]
•-100 <= Node.val <= 100
•Both list1 and list2 are sorted in non-decreasing order

예

Example 1

Input

[1,2,4], [1,3,4]

Output

[1,1,2,3,4,4]

Explanation

Merging 1->2->4 and 1->3->4 gives 1->1->2->3->4->4.

Example 2

Input

[], []

Output

[]

Explanation

Both lists are empty, so the merged list is also empty.

Example 3

Input

[], [0]

Output

[0]

Explanation

Merging an empty list with [0] gives [0].

Need a Hint?

세트나 힙과 같은 연결 목록 관련 데이터 구조를 사용하는 것을 고려해보세요.

Edge Cases to Watch

빈 입력 구조
단일 요소 입력
큰 수치 범위

해결할 준비가 되셨나요?

Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.

편집기에서 열기

인터뷰 통찰력 및 변형

연결 목록 접근 방식의 논리를 설명하십시오.

null 또는 빈 입력과 같은 극단적인 경우에 대해 논의합니다.

복잡성 분석 분석

무차별 대입 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Directly evaluates all possibilities.

왜 우주인가?: Uses standard local memory.

최적화된 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Optimized paths reduce total operations.

왜 우주인가?: May trade memory for speed.

최적화된 솔루션 Python 코드

컴파일러에서 시도해 보세요

def merge_two_lists_opt(list1, list2):
    if isinstance(list1, list):
        l1 = build_linked_list(list1)
        l2 = build_linked_list(list2)
        res = merge_two_lists_opt_helper(l1, l2)
        return linked_list_to_list(res)
    return merge_two_lists_opt_helper(list1, list2)

def merge_two_lists_opt_helper(list1: ListNode, list2: ListNode) -> ListNode:
    dummy = ListNode(0)
    tail = dummy
    while list1 and list2:
        if list1.val < list2.val:
            tail.next = list1
            list1 = list1.next
        else:
            tail.next = list2
            list2 = list2.next
        tail = tail.next
    tail.next = list1 or list2
    return dummy.next

무차별 대입 코드(스포일러 보호)

컴파일러에서 시도해 보세요

def merge_two_lists_brute(list1, list2):
    if isinstance(list1, list):
        l1 = build_linked_list(list1)
        l2 = build_linked_list(list2)
        res = merge_two_lists_brute_helper(l1, l2)
        return linked_list_to_list(res)
    return merge_two_lists_brute_helper(list1, list2)

def merge_two_lists_brute_helper(list1: ListNode, list2: ListNode) -> ListNode:
    vals = []
    curr = list1
    while curr:
        vals.append(curr.val)
        curr = curr.next
    curr = list2
    while curr:
        vals.append(curr.val)
        curr = curr.next
    vals.sort()
    
    dummy = ListNode(0)
    curr = dummy
    for v in vals:
        curr.next = ListNode(v)
        curr = curr.next
    return dummy.next