快捷導(dǎo)航

Python鏈表排序相關(guān)問(wèn)題解法示例

更新時(shí)間：2024年01月15日 09:52:04 作者：算法與編程之美

這篇文章主要為大家介紹了Python鏈表排序相關(guān)問(wèn)題解法示例,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪

問(wèn)題

鏈表實(shí)現(xiàn)選擇排列中經(jīng)常會(huì)遇到一些問(wèn)題，那么該如何解決它們呢？

方法

這一類問(wèn)題的基本都是根據(jù)題目給定的條件，對(duì)鏈表進(jìn)行各種組合，如：基于歸并排序思想，根據(jù)節(jié)點(diǎn)的數(shù)值，合并兩個(gè)鏈表（合并兩個(gè)排序的鏈表、合并k個(gè)已排序的鏈表）根據(jù)節(jié)點(diǎn)的位置，對(duì)鏈表重新排序（鏈表的奇偶重排）對(duì)兩個(gè)鏈表節(jié)點(diǎn)的數(shù)值相加（鏈表相加(二))

假設(shè)鏈表中每一個(gè)節(jié)點(diǎn)的值都在 0 - 9 之間，那么鏈表整體就可以代表一個(gè)整數(shù)。給定兩個(gè)這種鏈表，請(qǐng)生成代表兩個(gè)整數(shù)相加值的結(jié)果鏈表。

整體思路，如題目，鏈表的順序與加法的順序是相反的，自然的想到兩種思路：把鏈表的元素壓入棧中，借助棧實(shí)現(xiàn)對(duì)反轉(zhuǎn)鏈表的元素進(jìn)行操作；直接反轉(zhuǎn)鏈表由于兩種方式都需要新建鏈表，存儲(chǔ)兩個(gè)整數(shù)的相加值，因此空間復(fù)雜度都是o(n)。方法1比2多一個(gè)棧的空間，但是總的空間復(fù)雜度也是o(n)。細(xì)節(jié)提示加法的10進(jìn)制的進(jìn)位。設(shè)置進(jìn)位標(biāo)志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é)語(yǔ)

針對(duì)數(shù)組排序問(wèn)題，提出的解決方法，證明該方法是有效的。其實(shí)上面的題目的思路都很簡(jiǎn)單，相當(dāng)于把簡(jiǎn)單的排序從數(shù)組遷移到了鏈表中。個(gè)人認(rèn)為技巧在于鏈表節(jié)點(diǎn)的生成與穿針引線，一般可以使用兩個(gè)輔助節(jié)點(diǎn)，定義虛擬節(jié)點(diǎn)和游走節(jié)點(diǎn)，虛擬節(jié)點(diǎn)負(fù)責(zé)返回整個(gè)鏈表，游走節(jié)點(diǎn)負(fù)責(zé)穿針引線。以提高算法效率。

以上就是Python鏈表排序相關(guān)問(wèn)題解法示例的詳細(xì)內(nèi)容，更多關(guān)于Python鏈表排序問(wèn)題的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: