首页 > 试题广场 >

链式A+B

[编程题]链式A+B
  • 热度指数：43501 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

将两个反向存储在链表中的整数求和（即整数的个位存放在了链表首部，一位数对应一个节点），返回的结果仍用链表形式。

给定两个链表ListNode* A，ListNode* B，请返回A+B的结果(ListNode*)。

测试样例： 
{1,2,3},{3,2,1}
返回：{4,4,4}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
添加回答
推荐
念润头像 念润
思路

本题的思路很简单，按照小学数学中学习的加法原理从末尾到首位，对每一位对齐相加即可。技巧在于如何处理不同长度的数字，以及进位和最高位的判断。这里对于不同长度的数字，我们通过将较短的数字补0来保证每一位都能相加。

代码 
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;
    }
};

编辑于 2015-09-28 18:59:13 回复(5)
Python
牛客77233450号头像 牛客77233450号
我的思路是把两个链表中的节点依顺序分别放到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)
Python
l一人在山旁l头像 l一人在山旁l
通过转换做的，时间有点长，内存占用也大，但就是不想模拟-^-^- 
# -*- 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
华科平凡头像 华科平凡

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)
Python
Yannyezixin头像 Yannyezixin
思路很简单也很清晰, 两结点值跟进位相加，满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)
提交观点

问题信息

链表 基础数学
难度：
4条回答 35534浏览

热门推荐

通过挑战的用户

查看代码

相关试题

链式A+B

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号