题目概要

完成两个链表的“加法”并返回存储“和”的链表。

题目链接

Add Two Numbers

解题思路

1. 迭代两个链表，逐位相加
2. 相加过程中考虑进位
3. 注意两个链表不想等长度下，对长链表的处理

复杂度分析

时间复杂度：O(n)
空间复杂度：O(n)

代码

/**
 * 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) {
        if(!l1 && !l2) return NULL;
        if(!l1) return l2;
        if(!l2) return l1;
        int carry = 0;
        ListNode *head = new ListNode(0), *pre = head, *cur = head, *p1 = l1, *p2 = l2;
        head->val = p1->val + p2->val;
        carry = head->val / 10;
        head->val %= 10;
        pre->next = new ListNode(0);
        cur = pre->next;
        p1 = p1->next;
        p2 = p2->next;
        while(p1 && p2) {
            cur->val = carry + p1->val + p2->val;
            carry = cur->val / 10;
            cur->val %= 10;
            cur->next = new ListNode(0);
            pre = cur;
            cur = pre->next;
            p1 = p1->next;
            p2 = p2->next;
        }
        while(p1) {
            cur->val = carry + p1->val;
            carry = cur->val / 10;
            cur->val %= 10;
            cur->next = new ListNode(0);
            pre = cur;
            cur = pre->next;
            p1 = p1->next;
        }
        while(p2) {
            cur->val = carry + p2->val;
            carry = cur->val / 10;
            cur->val %= 10;
            cur->next = new ListNode(0);
            pre = cur;
            cur = pre->next;
            p2 = p2->next;
        }
        cur->val = carry;
        if(cur->val == 0) {
            delete pre->next;
            pre->next = NULL;
        }
        return head;
    }
};

广告区域

本人和小伙伴们承接各种软件项目，有需求的可以联系我们。
QQ: 2992073083