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

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

상위 150개 인터뷰쉬움

K개의 정렬된 목록 병합

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

문제 설명

쉬움

k개의 연결 목록 목록이 제공되며 각 연결 목록은 오름차순으로 정렬됩니다.

모든 연결된 목록을 하나의 정렬된 연결 목록으로 병합하고 반환합니다.

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

제약

•k == lists.length
•0 <= k <= 10000
•0 <= lists[i].length <= 500
•-10000 <= lists[i][j] <= 10000
•lists[i] is sorted in ascending order
•The sum of lists[i].length will not exceed 10000

예

Example 1

Input

[[1,4,5],[1,3,4],[2,6]]

Output

[1,1,2,3,4,4,5,6]

Explanation

Merging [1,4,5], [1,3,4], and [2,6] gives [1,1,2,3,4,4,5,6].

Example 2

Input

[]

Output

[]

Explanation

No lists to merge, so the result is empty.

Example 3

Input

[[]]

Output

[]

Explanation

One empty list results in an empty merged list.

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(n)

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

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

최적화된 솔루션 Python 코드

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

def merge_k_lists_opt(lists):
    if not lists: return []
    if isinstance(lists[0], list):
        nodes_list = [build_linked_list(l) for l in lists if l]
        res = merge_k_lists_opt_helper(nodes_list)
        return linked_list_to_list(res)
    return merge_k_lists_opt_helper(lists)

def merge_k_lists_opt_helper(lists) -> ListNode:
    import heapq
    heap = []
    for i, head in enumerate(lists):
        if head:
            heapq.heappush(heap, (head.val, i, head))
    dummy = ListNode(0)
    curr = dummy
    while heap:
        val, i, node = heapq.heappop(heap)
        curr.next = node
        curr = curr.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

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

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

def merge_k_lists_brute(lists):
    if not lists: return []
    if isinstance(lists[0], list):
        nodes_list = [build_linked_list(l) for l in lists if l]
        res = merge_k_lists_brute_helper(nodes_list)
        return linked_list_to_list(res)
    return merge_k_lists_brute_helper(lists)

def merge_k_lists_brute_helper(lists) -> ListNode:
    vals = []
    for l in lists:
        curr = l
        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