Python實現(xiàn)鏈表反轉與合并操作詳解
前言
使用 Python 實現(xiàn)反轉鏈表、合并鏈表在開發(fā)中比較常見，我們先來看看各自的應用場景。
1.反轉鏈表
比如，在處理時間序列數(shù)據(jù)時，有時需要將歷史數(shù)據(jù)按照時間從近到遠的順序展示，如果數(shù)據(jù)是以鏈表形式存儲的，通過反轉鏈表可以高效地實現(xiàn)這一需求。再比如，判斷一個鏈表是否為回文鏈表（即鏈表正序和逆序遍歷的值相同）時，可以先反轉鏈表的后半部分，然后與前半部分進行比較。再比如，在圖像處理中，有時需要對圖像進行水平或垂直翻轉。如果圖像數(shù)據(jù)以鏈表形式存儲（例如，鏈表中的每個節(jié)點代表圖像的一個像素），反轉鏈表可以實現(xiàn)圖像的水平翻轉。
2.合并鏈表
比如，在大規(guī)模數(shù)據(jù)排序中，當數(shù)據(jù)量太大無法一次性加載到內(nèi)存中時，可以采用多路歸并排序算法。該算法將數(shù)據(jù)分成多個小塊，分別排序后得到多個有序鏈表，然后通過合并這些有序鏈表得到最終的有序結果。合并鏈表是多路歸并排序的核心操作之一。在數(shù)據(jù)庫中，當執(zhí)行多個查詢操作并得到多個有序結果集時，需要將這些結果集合并成一個有序的結果集。如果這些結果集以鏈表形式存儲，合并鏈表可以高效地完成這個任務。在多媒體處理中，有時需要將多個音視頻流合并成一個流。如果每個音視頻流的數(shù)據(jù)以鏈表形式存儲，合并鏈表可以實現(xiàn)音視頻流的合并。
了解完反轉鏈表和合并鏈表的應用場景，是不是跟 V 哥一樣，這玩意兒還真挺有用的，那接下來，V 哥就詳細介紹一個反轉鏈表和合并鏈表。
反轉鏈表
先看在 Python 中實現(xiàn)反轉鏈表，我們可以使用迭代和遞歸兩種方法。下面分別給出這兩種方法的詳細實現(xiàn)。
迭代方法
迭代方法的核心思想是遍歷鏈表，在遍歷過程中改變每個節(jié)點的指針方向，使其指向前一個節(jié)點。
# 定義鏈表節(jié)點類
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseList(head):
# 初始化前一個節(jié)點為 None
prev = None
# 當前節(jié)點指向頭節(jié)點
curr = head
while curr:
# 保存當前節(jié)點的下一個節(jié)點
next_node = curr.next
# 將當前節(jié)點的指針指向前一個節(jié)點
curr.next = prev
# 前一個節(jié)點移動到當前節(jié)點
prev = curr
# 當前節(jié)點移動到下一個節(jié)點
curr = next_node
# 最終 prev 指向反轉后的頭節(jié)點
return prev
# 輔助函數(shù)：將列表轉換為鏈表
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ù)：將鏈表轉換為列表
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]
遞歸方法
遞歸方法的核心思想是先遞歸地反轉當前節(jié)點之后的鏈表，然后將當前節(jié)點的指針指向前一個節(jié)點。
# 定義鏈表節(jié)點類
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseList(head):
# 如果鏈表為空或只有一個節(jié)點，直接返回頭節(jié)點
if not head or not head.next:
return head
# 遞歸地反轉當前節(jié)點之后的鏈表
new_head = reverseList(head.next)
# 將當前節(jié)點的下一個節(jié)點的指針指向當前節(jié)點
head.next.next = head
# 將當前節(jié)點的指針置為 None
head.next = None
return new_head
# 輔助函數(shù)：將列表轉換為鏈表
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ù)：將鏈表轉換為列表
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]
以上兩種方法都可以實現(xiàn)鏈表的反轉，迭代方法的時間復雜度是 O(n)，空間復雜度是 O(1)；遞歸方法的時間復雜度也是 O(n)，但空間復雜度是 O(n)，主要是遞歸調(diào)用棧的開銷。
使用 Python 實現(xiàn)鏈表的合并
在 Python 中實現(xiàn)鏈表的合并，常見的情況有合并兩個有序鏈表和合并多個有序鏈表，下面分別介紹這兩種情況的實現(xiàn)方法。
合并兩個有序鏈表
合并兩個有序鏈表的思路是比較兩個鏈表當前節(jié)點的值，將較小值的節(jié)點添加到結果鏈表中，然后移動相應鏈表的指針，直到其中一個鏈表遍歷完，最后將另一個鏈表剩余的部分直接連接到結果鏈表的末尾。
# 定義鏈表節(jié)點類
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1, l2):
# 創(chuàng)建一個虛擬頭節(jié)點
dummy = ListNode(0)
# 當前節(jié)點指針，初始指向虛擬頭節(jié)點
current = dummy
while l1 and l2:
if l1.val <= l2.val:
# 如果 l1 的值較小，將 l1 節(jié)點添加到結果鏈表
current.next = l1
l1 = l1.next
else:
# 如果 l2 的值較小，將 l2 節(jié)點添加到結果鏈表
current.next = l2
l2 = l2.next
# 移動當前節(jié)點指針
current = current.next
# 將剩余的鏈表連接到結果鏈表末尾
if l1:
current.next = l1
if l2:
current.next = l2
# 返回合并后鏈表的頭節(jié)點（虛擬頭節(jié)點的下一個節(jié)點）
return dummy.next
# 輔助函數(shù)：將列表轉換為鏈表
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ù)：將鏈表轉換為列表
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]
合并多個有序鏈表
合并多個有序鏈表可以使用分治法，不斷地將鏈表兩兩合并，直到最終合并成一個鏈表。
# 定義鏈表節(jié)點類
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ù)：將列表轉換為鏈表
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ù)：將鏈表轉換為列表
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]
以上代碼分別實現(xiàn)了合并兩個有序鏈表和合并多個有序鏈表的功能，通過輔助函數(shù)可以方便地進行鏈表和列表之間的轉換，便于測試。
合并兩個鏈表的過程中，是否需要考慮鏈表為空的情況？
在合并兩個鏈表的過程中，需要考慮鏈表為空的情況，下面從必要性和不同實現(xiàn)情況來詳細分析：
必要性
考慮鏈表為空的情況是非常必要的，原因如下：
- 避免程序出錯：如果不處理鏈表為空的情況，在代碼中直接訪問空鏈表的節(jié)點屬性（如
val或next），會引發(fā)AttributeError異常，導致程序崩潰。 - 保證邏輯完整性：在實際應用中，鏈表為空是一種合理的輸入情況，處理這種邊界情況可以讓代碼更加健壯，能夠適應各種輸入場景。
不同實現(xiàn)情況的處理
合并兩個有序鏈表
下面是考慮鏈表為空情況的合并兩個有序鏈表的代碼：
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1, l2):
# 創(chuàng)建虛擬頭節(jié)點
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ù)：將列表轉換為鏈表
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ù)：將鏈表轉換為列表
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]
在上述代碼中，在函數(shù)開始處就對鏈表是否為空進行了判斷，如果其中一個鏈表為空，直接返回另一個鏈表。這樣可以避免后續(xù)代碼在訪問空鏈表節(jié)點時出現(xiàn)錯誤。
遞歸實現(xiàn)合并兩個有序鏈表
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ù)省略，同上面代碼
在遞歸實現(xiàn)中，同樣在函數(shù)開始就對鏈表為空的情況進行了處理，確保遞歸調(diào)用時不會出現(xiàn)訪問空節(jié)點屬性的錯誤。
所以，在合并兩個鏈表時，考慮鏈表為空的情況是必不可少的，這樣可以增強代碼的健壯性和可靠性。
最后
反轉鏈表和合并鏈表是鏈表操作中的基礎且重要的算法，在很多實際應用場景中都有廣泛的用途，就如 V 哥文章開頭介紹的應用場景，如果不懂應用場景來學鏈表反轉、合并，即使掌握了實現(xiàn)原理，也只是學會了招式，而不懂為什么學。
以上就是Python實現(xiàn)鏈表反轉與合并操作詳解的詳細內(nèi)容，更多關于Python鏈表的資料請關注腳本之家其它相關文章！
相關文章
Python實現(xiàn)OCR識別之pytesseract案例詳解
這篇文章主要介紹了Python實現(xiàn)OCR識別之pytesseract案例詳解,本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-07-07
150行Python代碼實現(xiàn)帶界面的數(shù)獨游戲
這篇文章主要介紹了150行Python代碼實現(xiàn)帶界面的數(shù)獨游戲,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-04-04
Python深度學習實戰(zhàn)PyQt5菜單和工具欄功能作用
本文詳細解讀通過 QtDesigner 創(chuàng)建主窗口、菜單欄和工具欄，并以菜單項 “退出” 為例關聯(lián)系統(tǒng)定義的動作處理方法。有需要的朋友可以借鑒參考下，希望能夠有所幫助2021-10-10
這篇文章主要為大家介紹一個簡單的Python暴力破解網(wǎng)站登錄密碼腳本，文中的過程講解詳細，對我們學習Python有一定的幫助，感興趣的可以學習一下2022-01-01
今天小編就為大家分享一篇把vgg-face.mat權重遷移到pytorch模型示例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-12-12
Python中unittest的數(shù)據(jù)驅動詳解
這篇文章主要介紹了Python中unittest的數(shù)據(jù)驅動詳解，數(shù)據(jù)驅動測試，是一種單元測試框架，文章圍繞主題展開詳細的內(nèi)容介紹，具有一定的參考價值，需要的小伙伴可以參考一下2022-08-08
Python?中如何使用requests模塊發(fā)布表單數(shù)據(jù)
requests 庫是 Python 的主要方面之一，用于創(chuàng)建對已定義 URL 的 HTTP 請求，本篇文章介紹了 Python requests 模塊，并說明了我們?nèi)绾问褂迷撃K在 Python 中發(fā)布表單數(shù)據(jù)，感興趣的朋友跟隨小編一起看看吧2023-06-06
在Pandas中,異常值是數(shù)據(jù)中那些與其他數(shù)據(jù)點顯著不同的點本文主要介紹了Pandas異常值處理小結,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2024-07-07
下面小編就為大家?guī)硪黄猵ython掃描proxy并獲取可用代理ip的實例。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-08-08
這篇文章主要為大家詳細介紹了如何利用Python3編寫一個簡易的電腦錄屏神器，文中的示例代碼講解詳細，感興趣的小伙伴可以動手嘗試一下2022-08-08