一、 题目描述:
假设链表中每一个节点的值都在 0 – 9 之间，那么链表整体就可以代表一个整数。 给定两个这种链表，请生成代表两个整数相加值的结果链表。
例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。
二、 解题思路:
(一)双栈法
本题的难点就在于如何按照正常的运算进行加法， 是使用栈(因为进栈的顺序为先进后出。最后一个栈项元素一定相当于各位那个数字)
1\就定义两个线，其中找1用来在放head1的元素，栈2用来存放head2的元素;
2\ 然后放光元素后。按照正常的加法递算进行求解了。
注意进位的情况。
class Solution:
def addInList(self , head1 , head2 ):
# write code here
s1,s2 = [],[]#用来存储两个链表的数据
while head1:#将head1的元素放入栈1
s1.append(head1.val)
head1 = head1.next
while head2:#将head2的元素放入栈2
s2.append(head2.val)
head2 = head2.next
res = None
cnt = 0#如果两个值的加和>10，就会产生进位，这个用来存储进位
while s1 or s2:
x1 = 0 if not s1 else s1.pop()
x2 = 0 if not s2 else s2.pop()
sum = x1 + x2 + cnt#当前这一位的总和
cnt = sum // 10 #查看当前加和是否有进位
#进行当前节点的插入
tempNode = ListNode(sum % 10)
tempNode.next = res
res = tempNode
#最后一位的时候还得判断当时是否有进位如果存在进位就得在插入一个元素
if cnt:
tempNode = ListNode(cnt)
tempNode.next = res
res = tempNode
return res
(二) 反转链表
#定义了反转链表
def ReverseList(self,pHead):
res = None
cur = pHead
while cur:
temp = cur.next
cur.next = res
res = cur
cur = temp
return res
def addInList(self , head1 , head2 ):
# write code here
l1 = self.ReverseList(head1)#翻转链表l1
l2 = self.ReverseList(head2)#翻转链表l2
res = None #用于返回的链表
cnt = 0#如果两个值的加和>10，就会产生进位，这个用来存储进位
while l1 or l2:
x1 = 0 if not l1 else l1.val
x2 = 0 if not l2 else l2.val
sum = x1 + x2 + cnt#当前这一位的总和
cnt = sum // 10#查看当前加和是否有进位
#进行当前节点的插入
tempNode = ListNode(sum % 10)
tempNode.next = res
res = tempNode
#链表的移动
l1 = None if not l1 else l1.next
l2 = None if not l2 else l2.next
#最后一位的时候还得判断当时是否有进位如果存在进位就得在插入一个元素
if cnt:
tempNode = ListNode(cnt)
tempNode.next = res
res = tempNode
return res
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/99764.html
