오늘 뭐 개발하지?

문제 링크 : leetcode.com/problems/merge-k-sorted-lists/

이 문제는 주어진 정렬된 linked list를 merge하여 하나의 linked list로 만드는 문제이다.

풀이방법

처음에는 n개의 linked list를 순회하여 가장 작은 값을 이전 값의 next로 연결하는 방식으로 구현하려고 했었는데 잘 되지 않아서 stack을 이용하는 방법으로 문제를 해결하였다. 처음엔 stack에 linked list의 node도 넣을 수 있나 싶었는데 역시 파이썬. 안되는 게 없다.

lists를 전부 순회하면서 각 linked list에 들어있는 요소들을 모두 stack에 저장한 후, lambda식을 이용하여 stack의 value를 기준으로 정렬한 후 각각의 node들을 연결시켜주었다.

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        head = ListNode()
        temp = head
        stack = []
        for i in lists:
            while i:
                stack.append(i)
                i = i.next
        stack = sorted(stack, key=lambda x:x.val, reverse=True)
        while stack:
            temp.next = stack.pop()
            temp = temp.next
        temp.next = None
        return head.next