快捷導(dǎo)航

Python實(shí)現(xiàn)鏈表反轉(zhuǎn)與合并操作詳解

更新時(shí)間：2025年02月20日 09:31:13 作者：威哥愛編程

這篇文章主要為大家詳細(xì)介紹了?Python?中反轉(zhuǎn)鏈表和合并鏈表的應(yīng)用場(chǎng)景及實(shí)現(xiàn)方法,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以了解下

前言

使用 Python 實(shí)現(xiàn)反轉(zhuǎn)鏈表、合并鏈表在開發(fā)中比較常見，我們先來(lái)看看各自的應(yīng)用場(chǎng)景。

1.反轉(zhuǎn)鏈表

比如，在處理時(shí)間序列數(shù)據(jù)時(shí)，有時(shí)需要將歷史數(shù)據(jù)按照時(shí)間從近到遠(yuǎn)的順序展示，如果數(shù)據(jù)是以鏈表形式存儲(chǔ)的，通過反轉(zhuǎn)鏈表可以高效地實(shí)現(xiàn)這一需求。再比如，判斷一個(gè)鏈表是否為回文鏈表（即鏈表正序和逆序遍歷的值相同）時(shí)，可以先反轉(zhuǎn)鏈表的后半部分，然后與前半部分進(jìn)行比較。再比如，在圖像處理中，有時(shí)需要對(duì)圖像進(jìn)行水平或垂直翻轉(zhuǎn)。如果圖像數(shù)據(jù)以鏈表形式存儲(chǔ)（例如，鏈表中的每個(gè)節(jié)點(diǎn)代表圖像的一個(gè)像素），反轉(zhuǎn)鏈表可以實(shí)現(xiàn)圖像的水平翻轉(zhuǎn)。

2.合并鏈表

比如，在大規(guī)模數(shù)據(jù)排序中，當(dāng)數(shù)據(jù)量太大無(wú)法一次性加載到內(nèi)存中時(shí)，可以采用多路歸并排序算法。該算法將數(shù)據(jù)分成多個(gè)小塊，分別排序后得到多個(gè)有序鏈表，然后通過合并這些有序鏈表得到最終的有序結(jié)果。合并鏈表是多路歸并排序的核心操作之一。在數(shù)據(jù)庫(kù)中，當(dāng)執(zhí)行多個(gè)查詢操作并得到多個(gè)有序結(jié)果集時(shí)，需要將這些結(jié)果集合并成一個(gè)有序的結(jié)果集。如果這些結(jié)果集以鏈表形式存儲(chǔ)，合并鏈表可以高效地完成這個(gè)任務(wù)。在多媒體處理中，有時(shí)需要將多個(gè)音視頻流合并成一個(gè)流。如果每個(gè)音視頻流的數(shù)據(jù)以鏈表形式存儲(chǔ)，合并鏈表可以實(shí)現(xiàn)音視頻流的合并。

了解完反轉(zhuǎn)鏈表和合并鏈表的應(yīng)用場(chǎng)景，是不是跟 V 哥一樣，這玩意兒還真挺有用的，那接下來(lái)，V 哥就詳細(xì)介紹一個(gè)反轉(zhuǎn)鏈表和合并鏈表。

反轉(zhuǎn)鏈表

先看在 Python 中實(shí)現(xiàn)反轉(zhuǎn)鏈表，我們可以使用迭代和遞歸兩種方法。下面分別給出這兩種方法的詳細(xì)實(shí)現(xiàn)。

迭代方法

迭代方法的核心思想是遍歷鏈表，在遍歷過程中改變每個(gè)節(jié)點(diǎn)的指針方向，使其指向前一個(gè)節(jié)點(diǎn)。

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

def reverseList(head):
    # 初始化前一個(gè)節(jié)點(diǎn)為 None
    prev = None
    # 當(dāng)前節(jié)點(diǎn)指向頭節(jié)點(diǎn)
    curr = head
    while curr:
        # 保存當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
        next_node = curr.next
        # 將當(dāng)前節(jié)點(diǎn)的指針指向前一個(gè)節(jié)點(diǎn)
        curr.next = prev
        # 前一個(gè)節(jié)點(diǎn)移動(dòng)到當(dāng)前節(jié)點(diǎn)
        prev = curr
        # 當(dāng)前節(jié)點(diǎn)移動(dòng)到下一個(gè)節(jié)點(diǎn)
        curr = next_node
    # 最終 prev 指向反轉(zhuǎn)后的頭節(jié)點(diǎn)
    return prev

# 輔助函數(shù)：將列表轉(zhuǎn)換為鏈表
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

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

# 測(cè)試代碼
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]

遞歸方法

遞歸方法的核心思想是先遞歸地反轉(zhuǎn)當(dāng)前節(jié)點(diǎn)之后的鏈表，然后將當(dāng)前節(jié)點(diǎn)的指針指向前一個(gè)節(jié)點(diǎn)。

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

def reverseList(head):
    # 如果鏈表為空或只有一個(gè)節(jié)點(diǎn)，直接返回頭節(jié)點(diǎn)
    if not head or not head.next:
        return head
    # 遞歸地反轉(zhuǎn)當(dāng)前節(jié)點(diǎn)之后的鏈表
    new_head = reverseList(head.next)
    # 將當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的指針指向當(dāng)前節(jié)點(diǎn)
    head.next.next = head
    # 將當(dāng)前節(jié)點(diǎn)的指針置為 None
    head.next = None
    return new_head

# 輔助函數(shù)：將列表轉(zhuǎn)換為鏈表
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

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

# 測(cè)試代碼
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]

以上兩種方法都可以實(shí)現(xiàn)鏈表的反轉(zhuǎn)，迭代方法的時(shí)間復(fù)雜度是 O(n)，空間復(fù)雜度是 O(1)；遞歸方法的時(shí)間復(fù)雜度也是 O(n)，但空間復(fù)雜度是 O(n)，主要是遞歸調(diào)用棧的開銷。

使用 Python 實(shí)現(xiàn)鏈表的合并

在 Python 中實(shí)現(xiàn)鏈表的合并，常見的情況有合并兩個(gè)有序鏈表和合并多個(gè)有序鏈表，下面分別介紹這兩種情況的實(shí)現(xiàn)方法。

合并兩個(gè)有序鏈表

合并兩個(gè)有序鏈表的思路是比較兩個(gè)鏈表當(dāng)前節(jié)點(diǎn)的值，將較小值的節(jié)點(diǎn)添加到結(jié)果鏈表中，然后移動(dòng)相應(yīng)鏈表的指針，直到其中一個(gè)鏈表遍歷完，最后將另一個(gè)鏈表剩余的部分直接連接到結(jié)果鏈表的末尾。

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

def mergeTwoLists(l1, l2):
    # 創(chuàng)建一個(gè)虛擬頭節(jié)點(diǎn)
    dummy = ListNode(0)
    # 當(dāng)前節(jié)點(diǎn)指針，初始指向虛擬頭節(jié)點(diǎn)
    current = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            # 如果 l1 的值較小，將 l1 節(jié)點(diǎn)添加到結(jié)果鏈表
            current.next = l1
            l1 = l1.next
        else:
            # 如果 l2 的值較小，將 l2 節(jié)點(diǎn)添加到結(jié)果鏈表
            current.next = l2
            l2 = l2.next
        # 移動(dòng)當(dāng)前節(jié)點(diǎn)指針
        current = current.next
    # 將剩余的鏈表連接到結(jié)果鏈表末尾
    if l1:
        current.next = l1
    if l2:
        current.next = l2
    # 返回合并后鏈表的頭節(jié)點(diǎn)（虛擬頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)）
    return dummy.next

# 輔助函數(shù)：將列表轉(zhuǎn)換為鏈表
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

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

# 測(cè)試代碼
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]

合并多個(gè)有序鏈表

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

# 定義鏈表節(jié)點(diǎn)類
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]

# 輔助函數(shù)：將列表轉(zhuǎn)換為鏈表
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

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

# 測(cè)試代碼
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]

以上代碼分別實(shí)現(xiàn)了合并兩個(gè)有序鏈表和合并多個(gè)有序鏈表的功能，通過輔助函數(shù)可以方便地進(jìn)行鏈表和列表之間的轉(zhuǎn)換，便于測(cè)試。

合并兩個(gè)鏈表的過程中，是否需要考慮鏈表為空的情況？

在合并兩個(gè)鏈表的過程中，需要考慮鏈表為空的情況，下面從必要性和不同實(shí)現(xiàn)情況來(lái)詳細(xì)分析：

必要性

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

避免程序出錯(cuò)：如果不處理鏈表為空的情況，在代碼中直接訪問空鏈表的節(jié)點(diǎn)屬性（如 val 或 next），會(huì)引發(fā) AttributeError 異常，導(dǎo)致程序崩潰。
保證邏輯完整性：在實(shí)際應(yīng)用中，鏈表為空是一種合理的輸入情況，處理這種邊界情況可以讓代碼更加健壯，能夠適應(yīng)各種輸入場(chǎng)景。

不同實(shí)現(xiàn)情況的處理

合并兩個(gè)有序鏈表

下面是考慮鏈表為空情況的合并兩個(gè)有序鏈表的代碼：

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

def mergeTwoLists(l1, l2):
    # 創(chuàng)建虛擬頭節(jié)點(diǎn)
    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

# 輔助函數(shù)：將列表轉(zhuǎn)換為鏈表
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

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

# 測(cè)試鏈表為空的情況
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]

在上述代碼中，在函數(shù)開始處就對(duì)鏈表是否為空進(jìn)行了判斷，如果其中一個(gè)鏈表為空，直接返回另一個(gè)鏈表。這樣可以避免后續(xù)代碼在訪問空鏈表節(jié)點(diǎn)時(shí)出現(xiàn)錯(cuò)誤。

遞歸實(shí)現(xiàn)合并兩個(gè)有序鏈表

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

# 輔助函數(shù)省略，同上面代碼

在遞歸實(shí)現(xiàn)中，同樣在函數(shù)開始就對(duì)鏈表為空的情況進(jìn)行了處理，確保遞歸調(diào)用時(shí)不會(huì)出現(xiàn)訪問空節(jié)點(diǎn)屬性的錯(cuò)誤。

所以，在合并兩個(gè)鏈表時(shí)，考慮鏈表為空的情況是必不可少的，這樣可以增強(qiáng)代碼的健壯性和可靠性。

最后

反轉(zhuǎn)鏈表和合并鏈表是鏈表操作中的基礎(chǔ)且重要的算法，在很多實(shí)際應(yīng)用場(chǎng)景中都有廣泛的用途，就如 V 哥文章開頭介紹的應(yīng)用場(chǎng)景，如果不懂應(yīng)用場(chǎng)景來(lái)學(xué)鏈表反轉(zhuǎn)、合并，即使掌握了實(shí)現(xiàn)原理，也只是學(xué)會(huì)了招式，而不懂為什么學(xué)。

以上就是Python實(shí)現(xiàn)鏈表反轉(zhuǎn)與合并操作詳解的詳細(xì)內(nèi)容，更多關(guān)于Python鏈表的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: