假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
给定两个这种链表，请生成代表两个整数相加值的结果链表。
数据范围：
，链表任意值 
要求：空间复杂度)
，时间复杂度
要求：空间复杂度
例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。
[编程题]链表相加(二)
# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param head1 ListNode类 # @param head2 ListNode类 # @return ListNode类 # class Solution: def addInList(self, head1: ListNode, head2: ListNode) -> ListNode: # write code here stack1, stack2, stack3 = [], [], [] while head1: stack1.append(head1.val) head1 = head1.next while head2: stack2.append(head2.val) head2 = head2.next carry = 0 while stack1&nbs***bsp;stack2&nbs***bsp;carry: if stack1: carry += stack1.pop() if stack2: carry += stack2.pop() stack3.append(carry % 10) carry //= 10 res = head = ListNode(0) while stack3: head.next = ListNode(stack3.pop()) head = head.next return res.next
编辑于 2024-01-31 21:19:03
回复(0)
class Solution: def addInList(self , head1: ListNode, head2: ListNode): # write code here # 反转链表 def reverse(root): prev = None head = root index = root while head != None: head = head.next index.next = prev prev = index index = head return prev p1 = reverse(head1) p2 = reverse(head2) head = None temp = 0 # 处理同位 头插法结果的头节点为head while p1 != None and p2 != None: print(p1.val) sum = p1.val + p2.val + temp node = ListNode(sum % 10) temp = sum // 10 node.next = head head = node p1 = p1.next p2 = p2.next # 处理高位 while p1 != None: sum = p1.val + temp node = ListNode(sum % 10) temp = sum // 10 node.next = head head = node p1 = p1.next while p2 != None: sum = p2.val + temp node = ListNode(sum % 10) temp = sum // 10 node.next = head head = node p2 = p2.next # 处理最后一个进位 if temp != 0: node = ListNode(temp) node.next = head head = node return head
发表于 2023-08-17 11:16:39
回复(1)
class Solution:
# 反转链表，按照个十百位数顺序相加，carry保存进位数据
# 时间复杂度：O(n) 空间复杂度：O(1)
def reverse_list(self, head):
if not head:
return None
cur = head
pre = None
while cur:
temp = cur.next
cur.next = pre
pre = cur
cur = temp
return pre
def addInList(self , head1: ListNode, head2: ListNode) -> ListNode:
if not head1:
return head2
if not head2:
return head1
head1 = self.reverse_list(head1)
head2 = self.reverse_list(head2)
res = ListNode(2022)
head = res
carry = 0
while head1 or head2 or carry != 0:
val1 = 0 if not head1 else head1.val
val2 = 0 if not head2 else head2.val
sum_ = val1 + val2 + carry
carry = sum_ // 10
temp = sum_ % 10
head.next = ListNode(temp)
head = head.next
if head1:
head1 = head1.next
if head2:
head2 = head2.next
return self.reverse_list(res.next)
发表于 2022-05-15 15:43:35
回复(0)
class Solution:
def addInList(self , head1: ListNode, head2: ListNode) -> ListNode:
# write code here
if head1 == None:
return head2
if head2 == None:
return head1
'''存入栈'''
s1, s2 = [], []
while head1:
s1.append(head1.val)
head1 = head1.next
while head2:
s2.append(head2.val)
head2 = head2.next
i = 0 # 进位值
temp = ListNode(0) # 链表尾部
while len(s1)>0 and len(s2)>0:
num1 = int(s1.pop())
num2 = int(s2.pop())
node = ListNode((num1 + num2 + i)%10) # 当前结果
i = (num1 + num2 + i)//10 # 更新进位值
node.next = temp.next # 头插法，将新生成的数插入到当前链表的头部
temp.next = node
while len(s1)>0:
num = int(s1.pop())
node = ListNode((num + i)%10)
i = (num + i)//10
node.next = temp.next
temp.next = node
if not s1 and i:
temp.val = i
while len(s2)>0:
num = int(s2.pop())
node = ListNode((num + i)%10)
i = (num + i)//10
node.next = temp.next
temp.next = node
if not s1 and i:
temp.val = i
return temp if temp.val else temp.next
发表于 2022-04-25 22:49:28
回复(0)
class Solution: def addInList(self , head1: ListNode, head2: ListNode) -> ListNode: # write code here if not head1: return head2 if not head2: return head1 #翻转 l1=head1 head1=head1.next l1.next=None while head1: dummy=head1.next head1.next=l1 l1=head1 head1=dummy #翻转 l2=head2 head2=head2.next l2.next=None while head2: dummy=head2.next head2.next=l2 l2=head2 head2=dummy #相加 pre=ListNode(0) cur=pre carry=0 while l1&nbs***bsp;l2: x=l1.val if l1 else 0 y=l2.val if l2 else 0 sum_value=int(x+y+carry) carry=sum_value//10 cur.next=ListNode((sum_value%10)) cur=cur.next if l1: l1=l1.next if l2: l2=l2.next if carry==1: cur.next=ListNode(1) #翻转 aim=pre.next l3=aim aim=aim.next l3.next=None while aim: dummy=aim.next aim.next=l3 l3=aim aim=dummy return l3
发表于 2022-01-07 01:34:47
回复(0)
写法有点笨，仅供参考，新手，求别骂。基本思路就是，遍历链表，用俩列表存起来，然后倒叙求和，再把剩下的一起求和，要考虑前后10的进位，用temp来存每次的这个进位，最后把整个列表倒叙，形成一个新的列表，再存到链表里
def addInList(self , head1 , head2 ): # write code here import math stack1 = [] stack2 = [] save = [] while(head1): stack1.append(head1.val) head1 = head1.next while(head2): stack2.append(head2.val) head2 = head2.next temp = 0 for i in range(-1,-(min(len(stack1),len(stack2))+1),-1): if(temp + stack1[i] + stack2[i]<10): save.append(temp + stack1[i] + stack2[i]) temp = 0 else: save.append((temp + stack1[i] + stack2[i])%10) temp = (temp + stack1[i] + stack2[i])//10 if(len(stack1)>len(stack2)): for j in range(-(min(len(stack1),len(stack2))+1),-(len(stack1)+1),-1): if((temp + stack1[j])<10): save.append(temp + stack1[j]) temp = 0 else: save.append((temp + stack1[j])%10) temp = 1 elif(len(stack2)>len(stack1)): for j in range(-(min(len(stack1),len(stack2))+1),-(len(stack2)+1),-1): if((temp + stack2[j])<10): save.append(temp + stack2[j]) temp = 0 else: save.append((temp + stack2[j])%10) temp = 1 if(temp == 1): save.append(1) save = save[::-1] newNode = ListNode(save[0]) temp = newNode for i in range(1,len(save)): newNode.next = ListNode(save[i]) newNode = newNode.next newNode.next = None return temp
发表于 2021-09-01 18:30:58
回复(0)
1先将链表分别存入栈中
2再从栈的末尾开始相加，记录进位值和当前结果
3使用头插法将结果存入结果链表中
class Solution: def addInList(self, head1, head2): # write code here if head1 == None: return head2 if head2 == None: return head1 '''存入栈''' s1, s2 = [], [] while head1: s1.append(head1.val) head1 = head1.next while head2: s2.append(head2.val) head2 = head2.next '''每次从栈末尾取出一个数进行相加，记录进位值并更新输出结果''' i = 0 # 进位值 temp = ListNode(0) # 链表尾部 while len(s1)>0 and len(s2)>0: num1 = int(s1.pop()) num2 = int(s2.pop()) node = ListNode((num1 + num2 + i)%10) # 当前结果 i = (num1 + num2 + i)//10 # 更新进位值 node.next = temp.next # 头插法，将新生成的数插入到当前链表的头部 temp.next = node '''处理其余特殊情况：s1先为空、s2先为空''' while len(s1)>0: num = int(s1.pop()) node = ListNode((num + i)%10) i = (num + i)//10 node.next = temp.next temp.next = node while len(s2)>0: num = int(s2.pop()) node = ListNode((num + i)%10) i = (num + i)//10 node.next = temp.next temp.next = node return temp.next
发表于 2021-07-24 14:32:08
回复(6)
问题信息
难度：
9条回答
990收藏
10132浏览
通过挑战的用户
查看代码-
2023-03-08 10:33:10 -
2023-02-04 19:27:02
-
2023-01-30 11:11:51
-
2023-01-20 01:16:08 -
2022-12-24 16:12:23
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
