23. Merge k Sorted Lists

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

input :

• lists

output :

• 모든 싱글 링크드 리스트의 원소를 오름차순으로 정렬한 head를 반환하시오.

조건 :

---

Solution explain : Solution1

idea 1

• 자료구조를 구현하듯이 포인터를 사용하자.
• 현재 비교를 하여 새롭게 추가될 원소를 now라고 지정한다.
• 비교군이 되어 이미 head에 들어있는 원소는 prev로 head에서 부터 순회할 것이다.
  
  
• 비어있지 않은 ListNode를 찾기 위한 반복문을 우선적으로 수행하고 이에 해당하는 것이 없다면 None을 반환한다.
• 해당 ListNode 다음의 노드 부터 순회를 시작하며 찾아야 하는 경우는 2가지 이다.
• 1. prev.val이 now.val 보다 더 작은 경우. (앞으로 들어가는 경우) => head의 변경
• 2. prev.val <= now.val <= prev.next.val인 경우 (중간에 들어가는 경우)
• 이렇게 하고 남은 값들이 있으면 다 뒤에 넣어주면 된다.
  
  
• 1의 경우
• temp_node를 만들어 next를 prev로 설정하고.
• head 변경 후 prev = temp_node로 설정을 하여 이전 노드를 설정한다.
  
  
• 2의 경우
• prev.next의 값을 저장해야 하기 때문에 이를 temp_next에 저장하고.
• temp_node를 만들어 prev.next = temp_node, temp_node.next = temp_next로 하여 순서를 설정한다.
• prev = prev.next로 하여 이동을 시킨다.
  
  
• 결국 언제나 prev = temp_node의 형태를 유지하며 이동한다.
• 제공되는 리스트의 형태가 정렬되어 있으므로 현재 들어가는 값 now보다 큰 값들만 이후에 나오게 된다.
• 그렇기에 처음부터 다시 순회를 하지 않아도 되는 것이다.

idea 2

• 모든 리스트 노드의 원소를 순회하며 해당 val를 리스트에 정렬한다.
• 값들을 다 연결시킨다....

주의

• 정렬이 싫다면 우선순위 큐를 사용해 뽑아내는 것도 하나의 방식이다.

# Definition for singly-linked list.
from typing import Optional, List


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    # def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    #     head = None
    #     for idx in range(len(lists)):
    #         if lists[idx]:
    #             head = lists[idx]
    #             break
    #
    #     if head is None:
    #         return head
    #
    #     for now in lists[idx + 1:]:
    #         prev = head
    #         while prev and now:
    #             if now.val < prev.val:
    #                 # 언제나 head가 바뀜
    #                 temp_node = ListNode(now.val, None)
    #                 temp_node.next = prev
    #                 head = temp_node
    #                 now = now.next
    #                 prev = temp_node
    #                 continue
    #
    #             if not prev.next:
    #                 break
    #
    #             if prev.val <= now.val <= prev.next.val:
    #                 temp_node = ListNode(now.val, None)
    #                 temp_next = prev.next
    #                 prev.next = temp_node
    #                 temp_node.next = temp_next
    #                 now = now.next
    #                 prev = prev.next
    #                 continue
    #             prev = prev.next
    #
    #         if not prev.next:
    #             prev.next = now
    #     return head
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        # 정렬
        head = None

        temp = []
        for now in lists:
            while now:
                temp.append(now.val)
                now = now.next
        temp.sort()

        if len(temp) == 0:
            return head

        head = ListNode(temp[0], None)
        now = head
        for i in range(1, len(temp)):
            temp_node = ListNode(temp[i], None)
            now.next = temp_node
            now = temp_node
        return head


# node2 = ListNode(5, None)
# node1 = ListNode(4, node2)
# node0 = ListNode(1, node1)
#
# node5 = ListNode(4, None)
# node4 = ListNode(3, node5)
# node3 = ListNode(1, node4)
#
# node8 = ListNode(6, None)
# node7 = ListNode(2, node8)

node27 = ListNode(7, None)
node26 = ListNode(4, node27)
node25 = ListNode(0, node26)
node24 = ListNode(-4, node25)

node17 = ListNode(7, None)
node16 = ListNode(5, node17)
node15 = ListNode(2, node16)
node14 = ListNode(1, node15)

node7 = ListNode(6, None)
node6 = ListNode(4, node7)
node5 = ListNode(3, node6)
node4 = ListNode(1, node5)
s = Solution()
ret = s.mergeKLists([node4, node14, node24])
while ret:
    print(ret.val, end=" ")
    ret = ret.next