<p/><p class="image-package"><img class="uploaded-img" src="https://upload-images.jianshu.io/upload_images/24755670-ce79e70d5decfead.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240" width="auto" height="auto"/><strong>题目描述</strong></p><p>给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储 一位 数字。</p><p>如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。</p><p>您可以假设除了数字 0 之外，这两个数都不会以 0 开头。</p><p>示例：</p><pre>输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807</pre><p><strong>题解</strong></p><p>备注:没有进行输入检查,默认是有效输入数据.</p><p><strong>按位依次累加</strong></p><p>首先观察数字和链表的对应方式:342--(2->4->3),在链表中,最低位是头节点,那么明显的,我们可以将两个链表按照顺序累加,同时需要注意会产生进位.</p><p>考虑到进位:</p><ol><li><p>获取链表上相同位数的元素并相加得到x如果之前上一个有进位标志,则x++,设置进位标志为false</p></li><li><p>判断x>=10,如果大于等于10,则需要x-=10,并且将进位标志重新设置成tre</p></li><li><p>创建节点等</p></li><li><p>在所有的值都处理完成后,如果进位标志是true,说明需要单独进位,如99+1 = 100.</p></li></ol><p>链表相加:</p><ol><li><p>两个链表从头开始,设置p1和p2来依次遍历</p></li><li><p>当p1和p2都不为nullptr时,可以同时遍历两个链表:p1 != nullptr && p2 != nullptr</p></li><li><p>如果p1和p2有一个走到了链表终点,即指向了nullptr,那么我们只需要遍历另外一个链表的剩余元素(需要考虑进位信息)</p></li></ol><pre>/**
Definition for singly-linked list.
struct ListNode {
int val;
ListNode next;
ListNode(int x) : val(x), next(NULL) {}
};
/
class Solution {
public:
ListNode addTwoNumbers(ListNode l1, ListNode l2) {
bool isOut = false; // 进位标志
ListNode p1 = l1;
ListNode *p2 = l2;
ListNode head = new ListNode(0); // 临时的头节点,用来悬挂后续节点
ListNode cur = head; // 当前节点
while (p1 != nullptr && p2 != nullptr) {
int x = p1->val + p2->val; // 计算和
if (isOut) // 如果上一个有进位,则x++,取消进位标志
{
x++;
isOut = false;
}
if (x >= 10) // 判断当前值是否溢出
{
x -= 10; // 溢出则-10,并且设置进位标志
isOut = true;
}
ListNode *tmp = new ListNode(x); // 构建节点
cur->next = tmp; // 悬挂在当前节点后面
cur = tmp; // 重设当前节点
p1 = p1->next;
p2 = p2->next;
}
// 获取到没有遍历完的list
ListNode *s = nullptr;
if (p1 != nullptr) s = p1;
if (p2 != nullptr) s = p2;
while (s != nullptr) {
int x = s->val; // 获取值
if (isOut) // 还需要结合进位标志判断
{
x++;
isOut = false;
}
if (x >= 10) {
x -= 10;
isOut = true;
}
ListNode *tmp = new ListNode(x);
cur->next = tmp;
cur = tmp;
s = s->next;
}
if (isOut) // 最后判断进位标志,如果还有,说明得单独创建一个节点
{
ListNode *tmp = new ListNode(1);
cur->next = tmp;
}
ListNode *r = head->next;
delete head;
return r;
}
};</pre><p>执行用时：32 ms, 在所有 C++ 提交中击败了81.51%的用户</p><p>内存消耗：9.1 MB, 在所有 C++ 提交中击败了75.31%的用户</p><p><strong>常见错误</strong></p><ol><li><p>将链表转换为数字,然后数字相加,最后将数字转为链表.在第一步转换数字的时候,链表可以存储超大数,但是数字类型<strong>long long</strong>等不一定能够存放下.</p></li><li><p>忘记考虑最后的一个进位标志.</p></li></ol><p>
</p>
