利用Python實現兩個鏈表合併為一個有序鏈表

對於開發工程師來說，實現兩個鏈表合併為一個有序鏈表是必須掌握的技能之一。Python語言在鏈表處理上非常便利，本文將從多個方面詳細闡述如何利用Python實現兩個鏈表合併為一個有序鏈表。

一、鏈表基礎知識

鏈表是一種常用的數據結構，由一系列節點組成。每個節點由數據和指向下一個節點的指針組成，最後一個節點的指針指向NULL。鏈表分為單向鏈表和雙向鏈表。

單向鏈表的每個節點只有一個指向下一個節點的指針，從頭節點往後遍歷；而雙向鏈表的每個節點有兩個指針，一個指向前一個節點，一個指向後一個節點，可以雙向遍歷。

二、合併兩個鏈表基本思路

假設有兩個單調不降鏈表，將它們合併為一個單調不降鏈表。

比較兩個鏈表的頭結點，將較小值的結點加入到新鏈表中，並將該結點從原鏈表頭結點剝離。之後再與另一個鏈表的頭結點進行比較，以此類推，直到其中一個鏈表為空，則將另一個鏈表的所有結點直接加入新鏈表中，最後得到一個有序鏈表。

三、實現代碼

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        head = ListNode(0)  # 定義一個啞節點
        pre = head

        while l1 and l2:
            if l1.val < l2.val:
                pre.next = l1
                l1 = l1.next
            else:
                pre.next = l2
                l2 = l2.next
            pre = pre.next  # 保留新鏈表的尾部

        pre.next = l1 if l1 else l2  # 處理剩餘節點

        return head.next

四、測試樣例

對代碼進行測試是不可缺少的環節，下面給出兩個鏈表測試樣例。

樣例1：

l1 = ListNode(1)
l1.next = ListNode(2)
l1.next.next = ListNode(4)

l2 = ListNode(1)
l2.next = ListNode(3)
l2.next.next = ListNode(4)

s = Solution()
res = s.mergeTwoLists(l1, l2)

while res:
    print(res.val, end=' ')
    res = res.next

輸出結果為：1 1 2 3 4 4

樣例2：

l1 = ListNode(-9)
l1.next = ListNode(3)

l2 = ListNode(5)
l2.next = ListNode(7)

s = Solution()
res = s.mergeTwoLists(l1, l2)

while res:
    print(res.val, end=' ')
    res = res.next

輸出結果為：-9 3 5 7

五、總結

本文詳細介紹了如何利用Python實現兩個鏈表合併為一個有序鏈表。通過對鏈表基礎知識和合併思路的講解，讀者可以更好地理解代碼實現。

值得注意的是，在進行鏈表操作時，一定要小心指針的使用，防止出現死循環或者空指針異常情況。