LeetCode高頻100題刷題記錄之——升序連結清單合并

1 思路分析

這題算是我在刷題的時候碰到的第一個大坑，坑的不是題目本身，而是連結清單結構在python中的結構，在python中，變量分為可變變量與不可變變量，比如這題的連結清單，就是一個不可變變量，給兩個符号賦相同的連結清單後，修改其中的一個，另一個會跟着改變，但又不是整個變量都改變了，而隻是對應結點位址處産生了變化，也是以最終可以實作連結清單的功能。

2 疊代法求解

這個代碼的思想是建立一個新的連結清單，來比較 l 1 l1 l1與 l 2 l2 l2中每個數的大小，最終将兩個連結清單中的所有數字按從小到大的規律排序送入 l 3 l3 l3中。這裡定義了一個$l3 _ ， 其 初 始 值 與 ，其初始值與 ，其初始值與l3 一 樣 ， 但 在 後 續 每 次 疊 代 時 ， 将 一樣，但在後續每次疊代時，将 一樣，但在後續每次疊代時，将l3 _ .next 中 的 值 使 用 中的值使用 中的值使用l1 與 與 與l2 中 最 小 的 那 個 替 換 ， 這 裡 ， 改 變 了 中最小的那個替換，這裡，改變了 中最小的那個替換，這裡，改變了l3 _ .next 指 向 的 地 址 的 數 值 ， 因 此 指向的位址的數值，是以 指向的位址的數值，是以l3$也被相應的改變了，也是以才能實作C語言中類似指針的效果。

這題真的是在實作上折磨了我很久，因為對python語言的不夠了解，導緻思路想清楚了但是一直做不出來，是以最後的代碼極大地參考了官方題解，但我個人的做題思路與官方題解是比較一緻的，但是實作不如官方題解整潔，是以下面的代碼與官方題解高度雷同，但好歹是學會了，但是連結清單的結構還應該好好地學習。

# 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, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 is None:
            return l2
        elif l2 is None:
            return l1
        else:
            l3 = ListNode()
            l3_ = l3

            while l1 and l2:
                if l1.val <= l2.val:
                    l3_.next = l1
                    l1 = l1.next
                else:
                    l3_.next = l2
                    l2 = l2.next
                l3_ = l3_.next
            
            l3_.next = l1 if l1 else l2  # 注意，是給next指派，而不是給目前的node指派
            return l3.next  # 因為是給next指派，是以最後l3的第一個元素是無關緊要的

           

3 遞歸法實作

使用遞歸其實不如使用疊代解這一題的效率高，但是學習遞歸的思想是很有必要的。

之前從沒使用過遞歸解決這個問題，是以這一題是寫法是參考了官方的題解以後，自己寫了一遍，過了三天再重新自己思考實作的。思路在于，判斷 l 1 l1 l1與 l 2 l2 l2是不是有空的，有就傳回另一個，這一點比較簡單，略去不說；遞歸部分，首先判斷一下兩個連結清單目前節點的值的大小，把小的那一個作為初始節點，然後對下一個節點繼續這樣的比較，直到指向最後一個節點，也就是None，每次疊代，連結清單都會指向i西安一個節點，是以可以周遊所有的節點，再一步步傳回比較後的結果，最終得到排序好的連結清單。

# 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, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 is None:
            return l2
        elif l2 is None:
            return l1
        else:
            if l1.val <= l2.val:
                l1.next = self.mergeTwoLists(l1.next, l2)
                return l1
            else:
                l2.next = self.mergeTwoLists(l1, l2.next)
                return l2