Python鏈表排序相關(guān)問題解法示例
問題
鏈表實現(xiàn)選擇排列中經(jīng)常會遇到一些問題，那么該如何解決它們呢？
方法
這一類問題的基本都是根據(jù)題目給定的條件，對鏈表進行各種組合，如：基于歸并排序思想，根據(jù)節(jié)點的數(shù)值，合并兩個鏈表（合并兩個排序的鏈表、合并k個已排序的鏈表）根據(jù)節(jié)點的位置，對鏈表重新排序（鏈表的奇偶重排）對兩個鏈表節(jié)點的數(shù)值相加（鏈表相加(二))
假設(shè)鏈表中每一個節(jié)點的值都在 0 - 9 之間，那么鏈表整體就可以代表一個整數(shù)。給定兩個這種鏈表，請生成代表兩個整數(shù)相加值的結(jié)果鏈表。
整體思路，如題目，鏈表的順序與加法的順序是相反的，自然的想到兩種思路：把鏈表的元素壓入棧中，借助棧實現(xiàn)對反轉(zhuǎn)鏈表的元素進行操作；直接反轉(zhuǎn)鏈表由于兩種方式都需要新建鏈表，存儲兩個整數(shù)的相加值，因此空間復(fù)雜度都是o(n)。方法1比2多一個棧的空間，但是總的空間復(fù)雜度也是o(n)。細節(jié)提示加法的10進制的進位。設(shè)置進位標志incre，每次循環(huán)判斷 val1 = list1.pop(-1)+list2.pop(-1)+incre。并且，在循環(huán)結(jié)束后，需要判斷incre是否>0，如果>0，需要在鏈表中增加
代碼清單
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def addInList(self , head1 , head2 ):
# write code here
list1 = []
while head1:
list1.append(head1.val)
head1 = head1.next
list2 = []
while head2:
list2.append(head2.val)
head2 = head2.next
list3 = []
incre = 0
while len(list1) and len(list2):
val1 = list1.pop(-1)+list2.pop(-1)+incre
incre = val1/10
val1 = val1%10
list3.append(val1)
while len(list1):
val1 = list1.pop(-1)+incre
incre = val1/10
val1 = val1%10
list3.append(val1)
while len(list2):
val1 = list2.pop(-1)+incre
incre = val1/10
val1 = val1%10
list3.append(val1)
if incre>0:
list3.append(incre)
dumpyNode = ListNode(-1)
pHead = dumpyNode
while len(list3):
pHead.next = ListNode(list3.pop(-1))
pHead = pHead.next
return dumpyNode.next
def addInList2(self , head1 , head2 ):
cur1 = head1
pre = None
while cur1:
next1 = cur1.next
cur1.next = pre
pre = cur1
cur1 = next1
head1 = pre
cur2 = head2
pre2 = None
while cur2:
next2 = cur2.next
cur2.next = pre2
pre2 = cur2
cur2 = next2
head2 = pre2
dumpyNode3 = ListNode(-1)
pHead = dumpyNode3
incre = 0
while head1 and head2:
val = head1.val+head2.val+incre
incre = val/10
val = val%10
head = ListNode(val)
pHead.next = head
pHead = pHead.next
head1 = head1.next
head2 = head2.next
while head1:
val = head1.val+incre
incre = val/10
val = val%10
head = ListNode(val)
pHead.next = head
pHead = pHead.next
head1 = head1.next
while head2:
val = head2.val+incre
incre = val/10
val = val%10
head = ListNode(val)
pHead.next = head
pHead = pHead.next
head2 = head2.next
if incre>0:
head = ListNode(incre)
pHead.next = head
pHead = pHead.next
pHead = dumpyNode3.next
cur1 = pHead
pre = None
while cur1:
next1 = cur1.next
cur1.next = pre
pre = cur1
cur1 = next1
return pre結(jié)語
針對數(shù)組排序問題，提出的解決方法，證明該方法是有效的。其實上面的題目的思路都很簡單，相當于把簡單的排序從數(shù)組遷移到了鏈表中。個人認為技巧在于鏈表節(jié)點的生成與穿針引線，一般可以使用兩個輔助節(jié)點，定義虛擬節(jié)點和游走節(jié)點，虛擬節(jié)點負責返回整個鏈表，游走節(jié)點負責穿針引線。以提高算法效率。
以上就是Python鏈表排序相關(guān)問題解法示例的詳細內(nèi)容，更多關(guān)于Python鏈表排序問題的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
這篇文章介紹了python的單元測試框架pytest，文中通過示例代碼介紹的非常詳細。對大家的學(xué)習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-06-06
Python把csv數(shù)據(jù)寫入list和字典類型的變量腳本方法
今天小編就為大家分享一篇Python把csv數(shù)據(jù)寫入list和字典類型的變量腳本方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-06-06
Python和Java的語法對比分析語法簡潔上python的確完美勝出
Python是一種廣泛使用的解釋型、高級編程、通用型編程語言，由吉多·范羅蘇姆創(chuàng)造，第一版發(fā)布于1991年。這篇文章主要介紹了Python和Java的語法對比，語法簡潔上python的確完美勝出 ,需要的朋友可以參考下2019-05-05
這篇文章主要為大家詳細介紹了Python數(shù)據(jù)可視化之繪制簡單折線圖的相關(guān)資料，文中的示例代碼簡潔易懂，感興趣的小伙伴可以了解一下2022-10-10
Requests是一個很實用的Python HTTP客戶端庫，編寫爬蟲和測試服務(wù)器響應(yīng)數(shù)據(jù)時經(jīng)常會用到，本文主要介紹了Python中requests做接口測試的方法，感興趣的可以了解一下2021-05-05
私有化是為了實現(xiàn)更好的封裝形式。能隱藏屬性，不被隨意修改。以前置雙下劃線__屬性/方法名定義，但是結(jié)尾不能是雙下劃線。如果不讓某些屬性在類外部被隨意更改，可設(shè)置成私有屬性。在類定義的內(nèi)部可以訪問2023-02-02
這篇文章主要介紹了python求crc32值的方法,包括相關(guān)的步驟及實現(xiàn)方法,需要的朋友可以參考下2014-10-10
PyInstaller可將Python代碼打包成單個可執(zhí)行文件,本文主要介紹了python打包pyinstall的實現(xiàn)步驟,具有一定的參考價值,感興趣的可以了解一下2023-10-10
Python實現(xiàn)將HTML表格一鍵導(dǎo)出為Excel
在數(shù)據(jù)處理和網(wǎng)頁爬蟲項目中,我們經(jīng)常會遇到從 HTML 頁面中提取表格的需求,本文將使用Python,BeautifulSoup和pandas實現(xiàn)一鍵將 HTML中的多個表格導(dǎo)出為Excel文件,需要的可以了解下2025-11-11
本文給大家分享了下作者是如何在linux下為python2.x以及python3.x安裝第三方庫的方法，十分的實用，有需要的小伙伴可以參考下2016-08-08