题目2–单链表求和

题目2–单链表求和

笔试题目:

1、用单向链表表示十进制整数,求两个正整数的和。如下图,1234+34=1268,
注意:单向链表的方向,不允许使用其他的数据结构
add_list

题目分析:

题目中提到了,数据结构只能使用单链表,所以数组不在考虑范围之内。
因为将数字转为单链表以后,最高位排在表头,而我们进行整数加法的时候,是从个位开始的,与单链表的顺序相反。所以我们考虑对链表进行反转,然后再做加法。

其中反转和求和的示意图如下:
reverse_add

对求和以后的结果再进行反转:
reverse_result

下面是C++的实现

代码解读

1.节点的数据结构定义如下:

2. 将int转为List

3.将List转为int

4. 释放节点内存

5 .实现链表的反转

6.将链表相加

主函数:

除非注明,否则均为浮生笔记原创文章,转载必须以链接形式标明本文链接

本文链接:https://www.dennisthink.com/2019/01/27/221/

Leave a Reply

Your email address will not be published. Required fields are marked *