博客 / 詳情

返回

Python 實現反轉、合併鏈表有啥用？

大家好，我是 V 哥。使用 Python 實現反轉鏈表、合併鏈表在開發中比較常見，我們先來看看各自的應用場景。先贊再看後評論，腰纏萬貫財進門。

  • 反轉鏈表

比如，在處理時間序列數據時，有時需要將歷史數據按照時間從近到遠的順序展示，如果數據是以鏈表形式存儲的，通過反轉鏈表可以高效地實現這一需求。再比如，判斷一個鏈表是否為迴文鏈表（即鏈表正序和逆序遍歷的值相同）時，可以先反轉鏈表的後半部分，然後與前半部分進行比較。再比如，在圖像處理中，有時需要對圖像進行水平或垂直翻轉。如果圖像數據以鏈表形式存儲（例如，鏈表中的每個節點代表圖像的一個像素），反轉鏈表可以實現圖像的水平翻轉。

  • 合併鏈表

比如，在大規模數據排序中，當數據量太大無法一次性加載到內存中時，可以採用多路歸併排序算法。該算法將數據分成多個小塊，分別排序後得到多個有序鏈表，然後通過合併這些有序鏈表得到最終的有序結果。合併鏈表是多路歸併排序的核心操作之一。在數據庫中，當執行多個查詢操作並得到多個有序結果集時，需要將這些結果集合併成一個有序的結果集。如果這些結果集以鏈表形式存儲，合併鏈表可以高效地完成這個任務。在多媒體處理中，有時需要將多個音視頻流合併成一個流。如果每個音視頻流的數據以鏈表形式存儲，合併鏈表可以實現音視頻流的合併。

瞭解完反轉鏈表和合並鏈表的應用場景，是不是跟 V 哥一樣，這玩意兒還真挺有用的，那接下來，V 哥就詳細介紹一個反轉鏈表和合並鏈表。

反轉鏈表

先看在 Python 中實現反轉鏈表，我們可以使用迭代和遞歸兩種方法。下面分別給出這兩種方法的詳細實現。

迭代方法

迭代方法的核心思想是遍歷鏈表，在遍歷過程中改變每個節點的指針方向，使其指向前一個節點。

# 定義鏈表節點類
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseList(head):
    # 初始化前一個節點為 None
    prev = None
    # 當前節點指向頭節點
    curr = head
    while curr:
        # 保存當前節點的下一個節點
        next_node = curr.next
        # 將當前節點的指針指向前一個節點
        curr.next = prev
        # 前一個節點移動到當前節點
        prev = curr
        # 當前節點移動到下一個節點
        curr = next_node
    # 最終 prev 指向反轉後的頭節點
    return prev

# 輔助函數：將列表轉換為鏈表
def list_to_linked_list(lst):
    dummy = ListNode(0)
    current = dummy
    for val in lst:
        current.next = ListNode(val)
        current = current.next
    return dummy.next

# 輔助函數：將鏈表轉換為列表
def linked_list_to_list(head):
    result = []
    current = head
    while current:
        result.append(current.val)
        current = current.next
    return result

# 測試代碼
input_list = [1, 2, 3, 4, 5]
head = list_to_linked_list(input_list)
reversed_head = reverseList(head)
output_list = linked_list_to_list(reversed_head)
print(output_list)  # 輸出: [5, 4, 3, 2, 1]

遞歸方法

遞歸方法的核心思想是先遞歸地反轉當前節點之後的鏈表，然後將當前節點的指針指向前一個節點。

# 定義鏈表節點類
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseList(head):
    # 如果鏈表為空或只有一個節點，直接返回頭節點
    if not head or not head.next:
        return head
    # 遞歸地反轉當前節點之後的鏈表
    new_head = reverseList(head.next)
    # 將當前節點的下一個節點的指針指向當前節點
    head.next.next = head
    # 將當前節點的指針置為 None
    head.next = None
    return new_head

# 輔助函數：將列表轉換為鏈表
def list_to_linked_list(lst):
    dummy = ListNode(0)
    current = dummy
    for val in lst:
        current.next = ListNode(val)
        current = current.next
    return dummy.next

# 輔助函數：將鏈表轉換為列表
def linked_list_to_list(head):
    result = []
    current = head
    while current:
        result.append(current.val)
        current = current.next
    return result

# 測試代碼
input_list = [1, 2, 3, 4, 5]
head = list_to_linked_list(input_list)
reversed_head = reverseList(head)
output_list = linked_list_to_list(reversed_head)
print(output_list)  # 輸出: [5, 4, 3, 2, 1]

以上兩種方法都可以實現鏈表的反轉，迭代方法的時間複雜度是 $O(n)$，空間複雜度是 $O(1)$；遞歸方法的時間複雜度也是 $O(n)$，但空間複雜度是 $O(n)$，主要是遞歸調用棧的開銷。

使用 Python 實現鏈表的合併

在 Python 中實現鏈表的合併，常見的情況有合併兩個有序鏈表和合並多個有序鏈表，下面分別介紹這兩種情況的實現方法。

合併兩個有序鏈表

合併兩個有序鏈表的思路是比較兩個鏈表當前節點的值，將較小值的節點添加到結果鏈表中，然後移動相應鏈表的指針，直到其中一個鏈表遍歷完，最後將另一個鏈表剩餘的部分直接連接到結果鏈表的末尾。

# 定義鏈表節點類
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(l1, l2):
    # 創建一個虛擬頭節點
    dummy = ListNode(0)
    # 當前節點指針，初始指向虛擬頭節點
    current = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            # 如果 l1 的值較小，將 l1 節點添加到結果鏈表
            current.next = l1
            l1 = l1.next
        else:
            # 如果 l2 的值較小，將 l2 節點添加到結果鏈表
            current.next = l2
            l2 = l2.next
        # 移動當前節點指針
        current = current.next
    # 將剩餘的鏈表連接到結果鏈表末尾
    if l1:
        current.next = l1
    if l2:
        current.next = l2
    # 返回合併後鏈表的頭節點（虛擬頭節點的下一個節點）
    return dummy.next

# 輔助函數：將列表轉換為鏈表
def list_to_linked_list(lst):
    dummy = ListNode(0)
    current = dummy
    for val in lst:
        current.next = ListNode(val)
        current = current.next
    return dummy.next

# 輔助函數：將鏈表轉換為列表
def linked_list_to_list(head):
    result = []
    current = head
    while current:
        result.append(current.val)
        current = current.next
    return result

# 測試代碼
list1 = [1, 2, 4]
list2 = [1, 3, 4]
l1 = list_to_linked_list(list1)
l2 = list_to_linked_list(list2)
merged_head = mergeTwoLists(l1, l2)
merged_list = linked_list_to_list(merged_head)
print(merged_list)  # 輸出: [1, 1, 2, 3, 4, 4]

合併多個有序鏈表

合併多個有序鏈表可以使用分治法，不斷地將鏈表兩兩合併，直到最終合併成一個鏈表。

# 定義鏈表節點類
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(l1, l2):
    dummy = ListNode(0)
    current = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next
    if l1:
        current.next = l1
    if l2:
        current.next = l2
    return dummy.next

def mergeKLists(lists):
    if not lists:
        return None
    while len(lists) > 1:
        merged_lists = []
        for i in range(0, len(lists), 2):
            l1 = lists[i]
            l2 = lists[i + 1] if i + 1 < len(lists) else None
            merged = mergeTwoLists(l1, l2)
            merged_lists.append(merged)
        lists = merged_lists
    return lists[0]

# 輔助函數：將列表轉換為鏈表
def list_to_linked_list(lst):
    dummy = ListNode(0)
    current = dummy
    for val in lst:
        current.next = ListNode(val)
        current = current.next
    return dummy.next

# 輔助函數：將鏈表轉換為列表
def linked_list_to_list(head):
    result = []
    current = head
    while current:
        result.append(current.val)
        current = current.next
    return result

# 測試代碼
lists = [[1, 4, 5], [1, 3, 4], [2, 6]]
linked_lists = [list_to_linked_list(lst) for lst in lists]
merged_head = mergeKLists(linked_lists)
merged_list = linked_list_to_list(merged_head)
print(merged_list)  # 輸出: [1, 1, 2, 3, 4, 4, 5, 6]

以上代碼分別實現了合併兩個有序鏈表和合並多個有序鏈表的功能，通過輔助函數可以方便地進行鏈表和列表之間的轉換，便於測試。

合併兩個鏈表的過程中，是否需要考慮鏈表為空的情況？

在合併兩個鏈表的過程中，需要考慮鏈表為空的情況，下面從必要性和不同實現情況來詳細分析：

必要性

考慮鏈表為空的情況是非常必要的，原因如下：

  • 避免程序出錯：如果不處理鏈表為空的情況，在代碼中直接訪問空鏈表的節點屬性（如 val 或 next），會引發 AttributeError 異常，導致程序崩潰。
  • 保證邏輯完整性：在實際應用中，鏈表為空是一種合理的輸入情況，處理這種邊界情況可以讓代碼更加健壯，能夠適應各種輸入場景。

不同實現情況的處理

合併兩個有序鏈表

下面是考慮鏈表為空情況的合併兩個有序鏈表的代碼：

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

def mergeTwoLists(l1, l2):
    # 創建虛擬頭節點
    dummy = ListNode(0)
    current = dummy
    # 處理鏈表為空的情況
    if not l1:
        return l2
    if not l2:
        return l1
    while l1 and l2:
        if l1.val <= l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next
    if l1:
        current.next = l1
    if l2:
        current.next = l2
    return dummy.next

# 輔助函數：將列表轉換為鏈表
def list_to_linked_list(lst):
    dummy = ListNode(0)
    current = dummy
    for val in lst:
        current.next = ListNode(val)
        current = current.next
    return dummy.next

# 輔助函數：將鏈表轉換為列表
def linked_list_to_list(head):
    result = []
    current = head
    while current:
        result.append(current.val)
        current = current.next
    return result

# 測試鏈表為空的情況
list1 = []
list2 = [1, 2, 3]
l1 = list_to_linked_list(list1)
l2 = list_to_linked_list(list2)
merged_head = mergeTwoLists(l1, l2)
merged_list = linked_list_to_list(merged_head)
print(merged_list)  # 輸出: [1, 2, 3]

在上述代碼中，在函數開始處就對鏈表是否為空進行了判斷，如果其中一個鏈表為空，直接返回另一個鏈表。這樣可以避免後續代碼在訪問空鏈表節點時出現錯誤。

遞歸實現合併兩個有序鏈表

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

def mergeTwoLists(l1, l2):
    # 處理鏈表為空的情況
    if not l1:
        return l2
    if not l2:
        return l1
    if l1.val <= l2.val:
        l1.next = mergeTwoLists(l1.next, l2)
        return l1
    else:
        l2.next = mergeTwoLists(l1, l2.next)
        return l2

# 輔助函數省略，同上面代碼

在遞歸實現中，同樣在函數開始就對鏈表為空的情況進行了處理，確保遞歸調用時不會出現訪問空節點屬性的錯誤。

所以，在合併兩個鏈表時，考慮鏈表為空的情況是必不可少的，這樣可以增強代碼的健壯性和可靠性。

最後

反轉鏈表和合並鏈表是鏈表操作中的基礎且重要的算法，在很多實際應用場景中都有廣泛的用途，就如 V 哥文章開頭介紹的應用場景，如果不懂應用場景來學鏈表反轉、合併，即使掌握了實現原理，也只是學會了招式，而不懂為什麼學。關注威哥愛編程，全棧開發就你行。

鏈表 , Python
user avatar
0 位用戶收藏了這個故事！

發佈 評論

Some HTML is okay.