将两个反向存储在链表中的整数求和（即整数的个位存放在了链表首部，一位数对应一个节点），返回的结果仍用链表形式。
给定两个链表ListNode* A，ListNode* B，请返回A+B的结果(ListNode*)。
测试样例：
{1,2,3},{3,2,1} 返回：{4,4,4}
[编程题]链式A+B
我的思路是把两个链表中的节点依顺序分别放到A和B两个字符串中，然后反转字符串，接着使用eval（），就能得到整数和，然后把这个整数和变成链表，不就ok了么，但是我的代码在我本地IDE能跑，为何在线跑不了？求大神帮忙看看
#链表的基础结构——链点 class ListNode: def __init__(self,x): self.val = x self.next = None #创建单链表 class LinkList: def __init__(self): self.head = None #创建单链表 def initlist(self,data_list): if data_list == []: self.head = None else: self.head = ListNode(data_list[0]) temp = self.head for i in data_list[1:]: node = ListNode(i) temp.next = node temp = temp.next return self.head class Plus: def plusAB(self, a, b): #这个为何通不过？ # write code here if not a&nbs***bsp;not b: return False else: A = '' B = '' while a: A += str(a.val) a = a.next while b: B += str(b.val) b = b.next C = str(eval(A[::-1]+'+'+B[::-1])) temp = [] for i in C[::-1]: temp.append(int(i)) new_link = LinkList() return new_link.initlist(temp)
发表于 2020-02-16 15:20:29
回复(0)
通过转换做的，时间有点长，内存占用也大，但就是不想模拟-^-^-
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Plus:
def plusAB(self, a, b):
arr1 = []
arr2 = []
print(type(a))
while a:
arr1.insert(0,str(a.val))
a = a.next
while b:
arr2.insert(0,str(b.val))
b = b.next
c = list(str(int(''.join(arr1))+int(''.join(arr2))))
newNode = ListNode(0)
newNode1 = newNode
for i in c[::-1]:
newNode.next = ListNode(int(i))
newNode = newNode.next
return newNode1.next
发表于 2019-02-19 19:11:28
回复(0)
python 解法.
思路很简单，我这种解法根本不用考虑进位和补位这种麻烦问题。
1、先把a和b表示的整数取出来
2.再计算两个数的和
3.把和表示为链表。
class Plus:
def plusAB(self, aHead, bHead):
# resA 和resB中放a和b的所有数字
resA, resB = [], []
while aHead:
resA.append(str(aHead.val))
aHead = aHead.next
while bHead:
resB.append(str(bHead.val))
bHead = bHead.next
# 计算a+b的和
result = str(int("".join(resA[::-1])) + int("".join(resB[::-1])))
#创建一个链表，从个位开始存放。
dummy = ListNode(0)
pre = dummy
for i in result[::-1]:
node = ListNode(int(i))
pre.next = node
pre = pre.next
return dummy.next
编辑于 2017-10-16 11:46:31
回复(1)
思路很简单也很清晰, 两结点值跟进位相加，满10进位1。
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Plus:
def plusAB(self, a, b):
if not a: return b
if not b: return a
carry = 0
head = p = ListNode(-1)
while a and b:
node = ListNode((a.val + b.val + carry)%10)
p.next = node
carry = 1 if (a.val + b.val + carry) >= 10 else 0
a, b, p = a.next, b.next, p.next
tmp = a if a else None
tmp = b if b else tmp
# 是否还有链表未迭代完
while tmp:
node = ListNode((tmp.val + carry)%10)
p.next = node
carry = 1 if (tmp.val + carry >= 10) else 0
p, tmp = p.next, tmp.next
# 是否还有进位
if carry:
node = ListNode(1)
p.next = node
p = p.next
p.next = None
return head.next
发表于 2016-08-02 09:24:34
回复(0)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
class Plus { public: ListNode* plusAB(ListNode* a, ListNode* b) { // 头结点 ListNode *head = new ListNode(-1); ListNode *p = head; ListNode *node = nullptr; int c = 0,sum,val1,val2; ListNode *pa = a,*pb = b; //加法 while(pa != nullptr || pb != nullptr || c != 0){ val1 = (pa == nullptr ? 0 : pa->val); val2 = (pb == nullptr ? 0 : pb->val); sum = val1 + val2 + c; // 进位 c = sum / 10; node = new ListNode(sum % 10); //尾插法 p->next = node; p = node; pa = (pa == nullptr ? nullptr : pa->next); pb = (pb == nullptr ? nullptr : pb->next); }//while return head->next; } };