[4코3파] #285. Leetcode 23. Merge k Sorted Lists

[4코3파] 1명의 스위프트 개발자가 도망가고 4명의 코틀린 개발자, 3명의 파이썬 개발자의 코딩 테스트 스터디 : 4코3파

START :

[3코1파] 2023.01.04~ (285일차)
[4코1파] 2023.01.13~ (277일차)
[4코3파] 2023.10.01 ~ (15일차)

Today :

2023.10.15 [285일차]

23. Merge k Sorted Lists

https://leetcode.com/problems/merge-k-sorted-lists/

문제 설명

k개의 링크드리스트가 담긴 배열이 주어 질때, 해당 링크드 리스트를 merge 했을 때 오름차순 정렬된 링크드 리스트를 반환하기

문제 풀이 방법

brute force로 푼다면 O(n*k) 이지만 리스트 내에 있는 링크드 리스트들을 두개씩 비교하고, 정렬해서 링크드 리스트를 만들고 또 나머지 두개 씩 비교한 링크드 리스트와 비교해서 정려한다면 O(nlogk)로 해결할 수 있다.

링크드 리스트를 두개씩 비교해서 정렬해서 리턴하는 새로운 메소드를 생성하는 것이 중요하다.
힙이나 다른 구조로도 풀 수 있지만, 링크드 리스트로만 푸는 방법은 아래와 같다.

내 코드

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
        
class Solution:
    def mergeKLists(self, lists: ListNode) -> ListNode:
        
        if not lists:
            return None
        
        while len(lists)>1:
            tmpList = []
            for i in range(0, len(lists),2):
                l1 = lists[i]
                l2 = lists[i+1] if (i+1) < len(lists) else None
                tmpList.append(self.mergeLists(l1, l2))
            lists = tmpList
            
        return lists[0]
                
    
    def mergeLists(self, l1: ListNode, l2:ListNode) -> ListNode:
        dummy = ListNode()
        node = dummy
        
        while l1 and l2:
            if l1.val < l2.val:
                node.next = l1
                l1 = l1.next
            else:
                node.next = l2
                l2 = l2.next
            node = node.next
            
        if l1:
            node.next = l1
        if l2:
            node.next = l2
        
        return dummy.next

증빙

여담

hard 치고는 상당히 이해하기 괜찮아서 좋았다