Python鏈表排序相關問題解法示例

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

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

問題

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

方法

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

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

整體思路，如題目，鏈表的順序與加法的順序是相反的，自然的想到兩種思路：把鏈表的元素壓入棧中，借助棧實現(xiàn)對反轉鏈表的元素進行操作；直接反轉鏈表由于兩種方式都需要新建鏈表，存儲兩個整數(shù)的相加值，因此空間復雜度都是o(n)。方法1比2多一個棧的空間，但是總的空間復雜度也是o(n)。細節(jié)提示加法的10進制的進位。設置進位標志incre，每次循環(huán)判斷 val1 = list1.pop(-1)+list2.pop(-1)+incre。并且，在循環(huán)結束后，需要判斷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

結語

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

以上就是Python鏈表排序相關問題解法示例的詳細內容，更多關于Python鏈表排序問題的資料請關注腳本之家其它相關文章！

您可能感興趣的文章: