题目描述
题目链接: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 contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
例子
例子 1
Input:
l1 = [2,4,3], l2 = [5,6,4]
Output:[7,0,8]
Explanation:342 + 465 = 807.
例子 2
Input:
l1 = [0], l2 = [0]
Output:[0]
例子 3
Input:
l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output:[8,9,9,9,0,0,0,1]
Constraints
- The number of nodes in each linked list is in the range
[1, 100]
.0 <= Node.val <= 9
- It is guaranteed that the list represents a number that does not have leading zeros.
解题思路
由于给定的两个链表都是逆序存放每一位的数字,所以我们同时遍历两个链表在遍历的过程中就可以把对应位置的数字相加(个位对个位,十位对十位,以此类推)。另外用一个布尔值判断是否含有进位即可,由于链表有可能不等长,因此其中只要还有一个链表没遍历都要继续遍历(为空的链表当作其值为 0 即可)。在两个链表都遍历完后要记得判断是否还含有进位,如果有的话还需要加一个额外的节点(值为 1)。
代码如下:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int len_diff = 0;
ListNode *curr1 = l1;
ListNode *curr2 = l2;
ListNode *dummy = new ListNode();
ListNode *curr_new = dummy;
bool has_one = false;
while (curr1 || curr2) {
int val1 = 0;
int val2 = 0;
if (curr1) {
val1 = curr1->val;
curr1 = curr1->next;
}
if (curr2) {
val2 = curr2->val;
curr2 = curr2->next;
}
int sum = val1 + val2;
if (has_one) {
sum++;
has_one = false;
}
if (sum >= 10) {
sum -= 10;
has_one = true;
}
curr_new->next = new ListNode(sum);
curr_new = curr_new->next;
}
if (has_one) {
curr_new->next = new ListNode(1);
}
return dummy->next;
}
};
- 时间复杂度: O(n)
- 空间复杂度: O(n) — 输出新的链表所需空间
GitHub 代码同步地址: 2.AddTwoNumbers.cpp
其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions