題目：

假設鏈表中每一個節點的值都在0~9之間，那么鏈表整體就可以代表一個整數。?
例如：9 -> 3 -> 7，可以代表整數937。?
給定兩個這種鏈表的頭節點head1和head2，請生成代表兩個整數相加值的結果鏈表。?
例如：鏈表1為9 -> 3 -> 7，鏈表2為6 -> 3，最后生成新的結果鏈表為1 -> 0 -> 0 -> 0。

基本思路：

容易想到的方法是先將兩個鏈表的值表示出來，然后將兩個值累加起來，再根據累加結果生成一個新鏈表。這種方法實際是不可行的，因為鏈表的長度可以很長，表示的數字可以很大，容易出現int類型溢出。

方法一。利用兩個棧，分別將鏈表1、2的值壓入棧中，這樣就生成了兩個鏈表的逆序棧。將兩個棧同時彈出，這樣就相當于兩個鏈表從低位到高位依次彈出，在這個過程中生成相加鏈表即可。注意相加過程中的進位問題。
?

class Node:def __init__(self,value):self.value = valueself.next = Nonedef addList(head1,head2):if head1 == None or head2 == None:return s1 = []s2 = []while head1!=None:s1.append(head1.value)head1 = head1.nextwhile head2!=None:s2.append(head2.value)head2 = head2.nextn1,n2,n,ca = 0,0,0,0pre,node = None,Nonewhile len(s1)!=0 or len(s2)!=0:if len(s1)==0:n1 = 0else:n1 = s1.pop()if len(s2)==0:n2 = 0else:n2 = s2.pop()n = n1 + n2 + capre = nodenode = Node(n%10)node.next = preca = n//10if ca == 1:pre = nodenode = Node(1)node.next = prereturn node """方法二、將鏈表逆序求解，可以節省棧空間"""def addList2(head1,head2):if head1 == None or head2 == None:returnhead1 = reverseList(head1)head2 = reverseList(head2)ca,n1,n2,n = 0,0,0,0c1,c2,node,pre = head1,head2,None,Nonewhile c1!=None or c2!=None:if c1!=None:n1 = c1.valueelse:n1 = 0if c2!=None:n2 = v2.valueelse:n2 = 0n = n1 + n2 + capre = nodenode = Node(n%10)node.next = preca = n//10if c1!=None:c1 = c1.nextelse:c1 = Noneif c2!=None:c2 = c2.nextelse:c2 = Noneif ca == 1:pre = nodenode = Node(1)node.next = prereverseList(head1)reverseList(head2)return nodedef reverseList(head):pre,next_ = None,Nonewhile head!=None:next_ = head.nexthead.next = prepre = headhead = next_return pre

?

總結

以上是生活随笔為你收集整理的两个单链表生成相加链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。