[Leetcode 23] - Merge k Sorted Lists w/ Python

문제

 

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. 

Merge all the linked-lists into one sorted linked-list and return it.

 

오름차순으로 정렬 되어 있는 연결 리스트의 배열이 주어졌다.

오름차순으로 정렬 되어 있는 한개의 연결 리스트로 만들어라!

 

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

 

 

---

 

 

예시

 

 

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

---

Example 2:

Input: lists = []
Output: []

---

 

Example 3:

Input: lists = [[]]
Output: []

 

 

 

---

 

 

풀이

 

연결 리스트 2개씩 합치는 방법이 제일 쉬워 보였다

(= k개의 연결 리스트를 한번에 하는건 복잡해 보였...다...)

 

 

class Solution:
    def mergeKLists(self, lists: List) -> Optional[ListNode]:
    	# 속도 개선!
        if not lists or len(lists) == 0:
            return None

        while len(lists) > 1:
            tempList = []

            for i in range(0, len(lists), 2): # 리스트 2개씩 합치기
                l1 = lists[i]
                l2 = lists[i + 1] if (i + 1) < len(lists) else None #홀수 방지용
                
                head = ListNode()
                curr = head
                while l1 and l2:
                    if l1.val < l2.val: # 값을 비교하고
                        curr.next = l1 # 바로 알맞는 곳으로 포인터 이동
                        l1 = l1.next
                    else:
                        curr.next = l2
                        l2 = l2.next
                    curr = curr.next
                
                if l1: curr.next = l1 # 남은 리스트가 l1 이라면
                if l2: curr.next = l2 # 남은 리스트가 l2 이라면

                tempList.append(head.next) # 일단 저장하고
            
            lists = tempList # 리스트를 수정한 후 while loop 컨디션 확인

        return lists[0]

 

 

 

결과!

 

 

연결 리스트에 조금씩 더 편해지는것 같다!

블로그 역시 작성하는게 조금씩 나아지는것 같다!