Lintcode221 Add Two Numbers II solution 题解
发布在LINTCODE2018年2月22日view:329
在文章任何区域双击击即可给文章添加【评注】!浮到评注点上可以查看详情。

【题目描述】

You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in forward order, such that the 1’s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.

假定用一个链表表示两个数,其中每个节点仅包含一个数字。假设这两个数的数字顺序排列,请设计一种方法将两个数相加,并将其结果表现为链表的形式。

【题目链接】

http://www.lintcode.com/en/problem/add-two-numbers-ii/

【题目解析】

我们看到这道题的最高位在链表首位置,可以看一些不修改链表顺序的方法。

由于加法需要从最低位开始运算,而最低位在链表末尾,链表只能从前往后遍历,没法取到前面的元素,那怎么办呢?我们可以利用栈来保存所有的元素,然后利用栈的后进先出的特点就可以从后往前取数字了,我们首先遍历两个链表,将所有数字分别压入两个栈s1和s2中,我们建立一个值为0的res节点,然后开始循环,如果栈不为空,则将栈顶数字加入sum中,然后将res节点值赋为sum%10,然后新建一个进位节点head,赋值为sum/10,如果没有进位,那么就是0,然后我们head后面连上res,将res指向head,这样循环退出后,我们只要看res的值是否为0,为0返回res->next,不为0则返回res即可。

【参考答案】

http://www.jiuzhang.com/solutions/add-two-numbers-ii/

评论
发表评论
暂无评论
PUBLISHED IN

我的收藏