[Leetcode解題] Merge Two Sorted Lists - 指針解

11 February 2022
easy linked-list pointer

題目

21. Merge Two Sorted Lists 給定兩個排的List: list1 和 list2。 將這兩個給定兩個排的List合併為一個排序的給定兩個排的List。合併的過程應該通過拼接第一個和第二個給定兩個排的List的節點完成。 返回合併後List的head。

解題思路

不論這兩條List有沒有排序過，都可以直接將這兩條List拼起來再做sort，這樣的時間複雜度是O(nlogn), n為兩條List總元素個數。 因為兩條List都是排序好的，因此可以試著運用這個特性，來減少計算量。

graphviz-5c36df7eb333dabf5c47e0e7fbebb9fb digraph { rankdir=LR ranksep=0.3 node [shape=box style="rounded,filled" height=0.3] node [label=1 fillcolor=pink] 1.1 node [label=2 fillcolor=pink] 1.2 node [label=4 fillcolor=pink] 1.4 node [label=1 fillcolor=lightgray] 2.1 node [label=3 fillcolor=lightgray] 2.3 node [label=4 fillcolor=lightgray] 2.4 node [label=5 fillcolor=lightgray] 2.5 node [ label="\N"] 1.1 -> 1.2 -> 1.4 2.1 -> 2.3 -> 2.4 -> 2.5 } 1.1 1 1.2 2 1.1->1.2 1.4 4 1.2->1.4 2.1 1 2.3 3 2.1->2.3 2.4 4 2.3->2.4 2.5 5 2.4->2.5

比較兩條排序好的list的第一個元素，將比較小的元素接到比較result後，直到至少有一條List為空

graphviz-f071932f24d170fccd5197c85ef29e8d digraph { rankdir=LR ranksep=0.3 node [shape=box style="rounded,filled" height=0.3] node [label=1 fillcolor=pink] 1.1 node [label=2 fillcolor=pink] 1.2 node [label=4 fillcolor=pink] 1.4 node [label=1 fillcolor=lightgray] 2.1 node [label=3 fillcolor=lightgray] 2.3 node [label=4 fillcolor=lightgray] 2.4 node [label=5 fillcolor=lightgray] 2.5 node [ label="\N"] 1.2 -> 1.4 2.1 ->2.3 -> 2.4 -> 2.5 result -> 1.1 } 1.1 1 1.2 2 1.4 4 1.2->1.4 2.1 1 2.3 3 2.1->2.3 2.4 4 2.3->2.4 2.5 5 2.4->2.5 result result result->1.1
graphviz-2f69f768b0e566db7e31a83c97a68a0a digraph { rankdir=LR ranksep=0.3 node [shape=box style="rounded,filled" height=0.3] node [label=1 fillcolor=pink] 1.1 node [label=2 fillcolor=pink] 1.2 node [label=4 fillcolor=pink] 1.4 node [label=1 fillcolor=lightgray] 2.1 node [label=3 fillcolor=lightgray] 2.3 node [label=4 fillcolor=lightgray] 2.4 node [label=5 fillcolor=lightgray] 2.5 node [ label="\N"] 1.2 -> 1.4 2.3 -> 2.4 -> 2.5 result -> 1.1 -> 2.1 } 1.1 1 2.1 1 1.1->2.1 1.2 2 1.4 4 1.2->1.4 2.3 3 2.4 4 2.3->2.4 2.5 5 2.4->2.5 result result result->1.1
graphviz-e7321849ecb8c5d5f6704b06ebcbe23b digraph { rankdir=LR ranksep=0.3 node [shape=box style="rounded,filled" height=0.3] node [label=1 fillcolor=pink] 1.1 node [label=2 fillcolor=pink] 1.2 node [label=4 fillcolor=pink] 1.4 node [label=1 fillcolor=lightgray] 2.1 node [label=3 fillcolor=lightgray] 2.3 node [label=4 fillcolor=lightgray] 2.4 node [label=5 fillcolor=lightgray] 2.5 node [ label="\N"] 1.4 2.3 -> 2.4 -> 2.5 result ->1.1 -> 2.1 -> 1.2 } 1.1 1 2.1 1 1.1->2.1 1.2 2 1.4 4 2.1->1.2 2.3 3 2.4 4 2.3->2.4 2.5 5 2.4->2.5 result result result->1.1
graphviz-07ae9dff2d93c5c40dfca31e988d9280 digraph { rankdir=LR ranksep=0.3 node [shape=box style="rounded,filled" height=0.3] node [label=1 fillcolor=pink] 1.1 node [label=2 fillcolor=pink] 1.2 node [label=4 fillcolor=pink] 1.4 node [label=1 fillcolor=lightgray] 2.1 node [label=3 fillcolor=lightgray] 2.3 node [label=4 fillcolor=lightgray] 2.4 node [label=5 fillcolor=lightgray] 2.5 node [ label="\N"] 1.4 2.4 -> 2.5 result ->1.1 -> 2.1 -> 1.2 -> 2.3 } 1.1 1 2.1 1 1.1->2.1 1.2 2 2.3 3 1.2->2.3 1.4 4 2.1->1.2 2.4 4 2.5 5 2.4->2.5 result result result->1.1

只剩下一條list還有元素，把這條list剩餘的元素按照順序直接放到result的最尾端

graphviz-46195296e7ba20176a0b8b7a0d70a6b0 digraph { rankdir=LR ranksep=0.3 node [shape=box style="rounded,filled" height=0.3] node [label=1 fillcolor=pink] 1.1 node [label=2 fillcolor=pink] 1.2 node [label=4 fillcolor=pink] 1.4 node [label=1 fillcolor=lightgray] 2.1 node [label=3 fillcolor=lightgray] 2.3 node [label=4 fillcolor=lightgray] 2.4 node [label=5 fillcolor=lightgray] 2.5 node [ label="\N"] 2.4 -> 2.5 result ->1.1 -> 2.1 -> 1.2 -> 2.3 -> 1.4 } 1.1 1 2.1 1 1.1->2.1 1.2 2 2.3 3 1.2->2.3 1.4 4 2.1->1.2 2.3->1.4 2.4 4 2.5 5 2.4->2.5 result result result->1.1

我們就成功把兩條排序好的List合成一條排序好的List了!!

graphviz-582ddff22645280afb50e811ec2f5c58 digraph { rankdir=LR ranksep=0.3 node [shape=box style="rounded,filled" height=0.3] node [label=1 fillcolor=pink] 1.1 node [label=2 fillcolor=pink] 1.2 node [label=4 fillcolor=pink] 1.4 node [label=1 fillcolor=lightgray] 2.1 node [label=3 fillcolor=lightgray] 2.3 node [label=4 fillcolor=lightgray] 2.4 node [ label="\N"] result ->1.1 -> 2.1 -> 1.2 -> 2.3 -> 1.4 -> 2.4 -> 2.5 } 1.1 1 2.1 1 1.1->2.1 1.2 2 2.3 3 1.2->2.3 1.4 4 2.4 4 1.4->2.4 2.1->1.2 2.3->1.4 2.5 2.5 2.4->2.5 result result result->1.1

實作

# 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]:
        cr = mergeList = ListNode()
        while list1 and list2:
            if list1.val < list2.val:
                cr.next = list1
                list1 = list1.next
                cr = cr.next
            else:
                cr.next = list2
                list2 = list2.next
                cr = cr.next
        
        cr.next = list1 if list1 else list2
        return mergeList.next