图解 LeetCode 链表: 2. Add Two Numbers

今天是 LeetCode 算法的 第 1 阶段第 4 天 ，这一阶段主要学习链表相关的算法题和链表数据结构。

2. Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Explanation: 342 + 465 = 807.

分析

给定两个单链表 L1 和 L2，L1 逆序保存了第一个整数，比如 342，对应的链表为 2->4->3；L2 逆序保存了第二个整数，比如 465，对应的链表为 6->5->4。对链表中的每个节点元素进行相加，相加结果保存到另一个链表中：

代码

两个链表表示两个整数，而且在链表中逆序存储，这使得两个数相加更加简单，如果两个列表节点的和大于等于10，将进一位，如同整数相加原理一样。C++ 实现如下：

结果

Runtime: 28 ms, faster than 97.22% of C++ online submissions for Add Two Numbers. Memory Usage: 10.5 MB, less than 98.48% of C++ online submissions for Add Two Numbers.

总结

这道题你也许想把两个链表转换成整数，然后把这两个整数进行相加，把结果转换成链表。这种思路将大错特错，如果数字太大将发生栈溢出，

runtime error: signed integer overflow: 1000000000 * 9 cannot be represented in type 'int' 。

本题涉及到了对链表的遍历和创建。

文中涉及到的算法代码，我在GitHub创建了一个项目 LeetCodeGraphically，点击阅读原文即可查看。

下一道题目留给你思考，反转单链表：

206. Reverse Linked List

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL