문제

• sorted linked list 2개가 주어짐
• one sorted 로 연결

풀이

heap 정렬

• 노드를 새로 만들지 않고, 본래의 노드를 그대로 이용
• heapq를 이용해서 풀이

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        heap = []
        while list1.next:
            heappush(heap, [list1.val, list1])
        while list2.next:
            heappush(heap, [list2.val, list2])
        
        head = heappop(heap)[1]
        thisNode = head
        while heap:
            nextNode = heappop(heap)
            thisNode.next = nextNode
            thisNode = nextNode
        return head

ㅇㅋ,,,,

리스트에 다른 리스트를 삽입

• 굳이 두개 다 정렬하지 말고, 이미 정렬되어 있으니까 껴넣기만하자!!!!
• head를 비교해서, 작은걸 답의 head로

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if list1 and list2:
            baseList = list1 if list1.val < list2.val else list2
            insertingList = list2 if list1.val < list2.val else list1

            head = baseList

            while insertingList and baseList.next:
                if baseList.val <= insertingList.val <= baseList.next.val:
                    insertingNode = insertingList
                    insertingList = insertingList.next

                    insertingNode.next = baseList.next  # 뒷 부분 연결
                    baseList.next = insertingNode  # 앞부분 연결
                    baseList = baseList.next
                else:
                    baseList = baseList.next

            # 마지막 연결
            if insertingList:
                # baseList.next == None 인데 while 이 종료
                baseList.next = insertingList


            return head
        elif list1:
            return list1
        else:
            return list2

아 리트코드 맨날 empty list를 인풋으로 줘서 예외처리 꼭 해야한다...;
조건을 잘 봐야하는데...

결과