[2021][01]Merge K sorted Lists
問題情報
問題の概要
k個の昇順に並べられた接続リストが与えられると、すべての接続リストが1つの接続リストに結合され、1つの接続リストが返される.
せいげんじょうけん
方法
問題を見て最初に考えた方法は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 answerReference
この問題について([2021][01]Merge K sorted Lists), 我々は、より多くの情報をここで見つけました https://velog.io/@papayetoo/202101Merge-K-sorted-Listsテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol