今天是 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