← 전체 회차
A-044● Day 442026.06.19hardleetcode #23neetcode150

k개 정렬 리스트 병합

#linked-list#divide-and-conquer#heap-priority-queue#merge-sort
↗ leetcode #23 · merge-k-sorted-lists
01

문제

· problem
P.044

k개 정렬 리스트 병합

↗ leetcode #23

k개의 링크드 리스트로 이루어진 배열 lists가 주어집니다. 각 링크드 리스트는 오름차순으로 정렬되어 있습니다. 모든 링크드 리스트를 하나의 정렬된 링크드 리스트로 병합하고 반환하세요.

제약
  • · 0 ≤ k ≤ 10^4 (number of lists)
  • · 0 ≤ lists[i].length ≤ 500 (per-list node count)
  • · -10^4 ≤ lists[i][j] ≤ 10^4 (node values range)
  • · Each list sorted in ascending order
  • · Total nodes across all lists ≤ 10^4
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
[[1,4,5],[1,3,4],[2,6]]
[1,1,2,3,4,4,5,6]
example 2input → output
[]
[]
example 3input → output
[[]]
[]
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    각 리스트가 가장 작은 값부터 가장 큰 값 순서로 정렬되어 있다는 의미인가요?
  • ☐
    입력 배열이 완전히 비어있는 경우(k=0)는 어떻게 처리하나요?
  • ☐
    개별 리스트가 비어있을 수 있나요(예: lists = [[]])?
  • ☐
    노드의 값이 음수일 수 있나요?
  • ☐
    모든 리스트의 총 노드 수 최댓값은?
  • ☐
    입력 리스트에 사이클이 있을 수 있나요?
  • ☐
    결과는 내림차순으로 정렬되어야 하나요?
  • ☐
    원본 입력 리스트를 수정할 수 없나요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 빈 입력 처리
○
if not lists or len(lists) == 0:
○
if len(lists) == 0:
○
if lists:
step 2· 병합 반복 루프 조건
○
while len(lists) > 1:
○
while len(lists) > 0:
○
while len(lists) >= 1:
step 3· 2씩 증가하는 인덱스 반복│ 중첩
○
for i in range(0, len(lists), 2):
○
for i in range(0, len(lists)):
○
for i in range(len(lists)//2):
step 4· 홀수 개 리스트 경계 처리│ │ 중첩
○
l2 = lists[i + 1] if (i + 1) < len(lists) else None
○
l2 = lists[i + 1]
○
l2 = lists[i + 1] if i + 1 < len(lists) - 1 else None
step 5· 병합 결과를 새 배열에 저장│ │ 중첩
○
mergedLists.append(self.mergeList(l1, l2))
○
lists.append(self.mergeList(l1, l2))
○
mergedLists.extend([l1, l2])
step 6· 다음 라운드 입력 준비│ 중첩
○
lists = mergedLists
○
mergedLists = lists
○
lists.extend(mergedLists)
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
# Definition for singly-linked list.
2
# class ListNode:
3
#     def __init__(self, val=0, next=None):
4
#         self.val = val
5
#         self.next = next
6
class Solution:
7
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
8
        if not lists or len(lists) == 0:
9
            return None
10
11
        while len(lists) > 1:
12
            mergedLists = []
13
            for i in range(0, len(lists), 2):
14
                l1 = lists[i]
15
                l2 = lists[i + 1] if (i + 1) < len(lists) else None
16
                mergedLists.append(self.mergeList(l1, l2))
17
            lists = mergedLists
18
        return lists[0]
19
20
    def mergeList(self, l1, l2):
21
        dummy = ListNode()
22
        tail = dummy
23
24
        while l1 and l2:
25
            if l1.val < l2.val:
26
                tail.next = l1
27
                l1 = l1.next
28
            else:
29
                tail.next = l2
30
                l2 = l2.next
31
            tail = tail.next
32
        if l1:
33
            tail.next = l1
34
        if l2:
35
            tail.next = l2
36
        return dummy.next
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
[[1,4,5],[1,3,4],[2,6]]
→
[1,1,2,3,4,4,5,6]
case 2
[]
→
[]
case 3
[[]]
→
[]
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.