[2021][01]Merge K sorted Lists

問題情報

問題の概要

k個の昇順に並べられた接続リストが与えられると、すべての接続リストが1つの接続リストに結合され、1つの接続リストが返される.

せいげんじょうけん

k == lists.length

0 <= k <= 10^4

0 <= lists[i].length <= 500

-10^4 <= lists[i][j] <= 10^ 4

lists[i]昇順で

に接続

各リスト[i]の長さの和は10^4である.

を超えない

方法

問題を見て最初に考えた方法はlist[i]で最小値のlistNodeをループし、list[i]のポインタを検索することですか?現在位置を表すListNodeをnextに移動し、このように統合する方法を考えたことがあります.この方法では難しいと思うのは、すべてのlist[i]に対して、少なくともvalを持つlist[i]を見つけるのが難しいことだ.Divide and Conquerで問題を解決した後,他人の優先順位キューソリューションを利用することが,この考えを具体化したソリューションである.
パーティション化とConquer方式のプールは,そのプールのK個の接続リストが与えられても,最も基本的な場合は2個の接続リストをマージすると考えられる.したがって、2つの接続リストをマージする関数を作成し、kつの接続リストに対してこの関数を実行して、問題に必要な結果を返すことができます.

from typing import List

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:

        def helper(l: ListNode, r: ListNode) -> ListNode:
        	# 2개의 오름차순 정렬된 연결리스트를 하나로 합치는 함수.
            answer = ListNode()
            res = answer
            curL = l
            curR = r
            while curL and curR:
                if curL.val > curR.val:
                    res.next = curR
                    res = res.next
                    curR = curR.next
                    continue
                else:
                    res.next = curL
                    res = res.next
                    curL = curL.next
                    continue

            if curL:
                res.next = curL

            if curR:
                res.next = curR

            return answer.next

        k = len(lists)
        # 시작할 때 처음 answer = None과 다음 연결리스트를 병합해서
        # answer에 그 병합된 결과를 반환하면 k개의 연결리스트를 병합한 결과를 얻을 수 있음.
        answer = None
        for i in range(k):
            answer = helper(answer, lists[i])
        return answer