LeetCode题解-AddTwoNumbers
LeetCode题解-AddTwoNumbers
卡尔曼和玻尔兹曼谁曼
发布于 2019-01-22 09:44:49
发布于 2019-01-22 09:44:49
LeetCode题解-AddTwoNumbers
问题描述
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的指针走到了最末尾 - 两个列表的指针指向都已经为空
其中第2，3，4中情况需要特殊处理
还有需要注意的是：两个数字相加大于10的情况，后面的结果需要加上1（这个可以通过设置一个旗帜变量解决）
代码实现
C++版本
// ListNode的定义
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
// 通过给定的数据创建一个ListNode列表
ListNode *createList(vector<int> &nums) {
ListNode *head = new ListNode(0);
ListNode *current = head;
for (auto iter = nums.begin(); iter != nums.end();) {
current->val = *iter;
if (++iter != nums.end())
current->next = new ListNode(0);
else
current->next = nullptr; // 如果是最后一个数据了，则next指向为NULL
current = current->next;
}
return head;
}
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
ListNode *p1 = l1;
ListNode *p2 = l2;
ListNode *head = new ListNode(0);
ListNode *current = head;
int sum = 0;
int flag = 0;
while (p1 || p2 || flag) {
sum = (p1 ? p1->val : 0) + (p2 ? p2->val : 0);
if (flag == 1) {
sum += 1;
flag = 0;
}
if (sum >= 10) {
sum %= 10;
flag = 1;
}
current->val = sum;
p1 = p1 ? p1->next : p1;
p2 = p2 ? p2->next : p2;
if (p1 || p2 || flag)
current->next = new ListNode(0);
else
current->next = nullptr;
current = current->next;
}
return head;
}
int main() {
vector<int> v1 = {5};
vector<int> v2 = {5};
ListNode *l1 = createList(v1);
ListNode *l2 = createList(v2);
ListNode *ls = addTwoNumbers(l1, l2);
while (ls) {
cout << ls->val << ' ';
ls = ls->next;
}
cout << endl;
return 0;
}Scala版本
感觉函数式编程语言真的有时候很简洁，让编程完全换了一种思路
下面Scala版本的实现没有采用LeetCode定义的ListNode结构，而是直接使用Scala本身提供的List实现的
通过使用模式匹配，分列出来可能出现的四种情况，然后通过递归依次遍历两个列表，将每次计算的结果放在前面
体验一下函数式编程的简介之处吧！
package leetcode
object AddTwoNumbers {
def addTwoNumbers(l1: List[Int], l2: List[Int]): List[Int] = {
def addWithCarry(lists: (List[Int], List[Int]), carry: Int) = lists match {
case (Nil, Nil) => if (carry == 0) Nil else List(carry)
case (x :: xtail, Nil) => addHeads(x, 0, carry, (xtail, Nil))
case (Nil, y :: ytail) => addHeads(0, y, carry, (Nil, ytail))
case (x :: xtail, y :: ytail) => addHeads(x, y, carry, (xtail, ytail))
}
def addHeads(x: Int, y: Int, carry: Int, tails: (List[Int], List[Int])): List[Int] = {
val sum = x + y + carry
// 每次的计算结果放在前面，后面采用递归依次计算
sum % 10 :: addWithCarry(tails, sum / 10)
}
addWithCarry((l1, l2), 0)
}
def main(args: Array[String]): Unit = {
val l1 = List(2, 4, 3)
val l2 = List(5, 6, 4)
val ls = addTwoNumbers(l1, l2)
ls.foreach(print(_))
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018年06月08日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录