質問する

には、2つの並べ替えられたチェーンテーブル

がある.

one

に順次接続する.

に答える

ヒープのソート

ノードを新規作成するのではなく、元のノード

を使用します.

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

Arite Codeは毎日空リストをくれているので、例外処理をしなければなりません...;
条件をよく見てください.

結果