两数相加¶

难度：中等
链接：https://leetcode-cn.com/problems/add-two-numbers/

标签：Linked List, Math

描述¶

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入: (2 -> 4 -> 3) + (5 -> 6 -> 4)
输出: 7 -> 0 -> 8
原因: 342 + 465 = 807

题解¶

同时遍历两个链表，考虑进位和链表长度不一致的情况。

新链表的值为 \((n1+n2+carry)\%10\) , 进位 carry 值为 \((n1+n2+carry)/10\)

C

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     struct ListNode *next;
* };
*/
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
    struct ListNode* head = NULL;
    struct ListNode* tail = NULL;
    int carry = 0;
    while (l1 || l2) {
        int n1 = l1 ? l1->val : 0;
        int n2 = l2 ? l2->val : 0;
        int n = n1 + n2 + carry;
        if(head == NULL) {
            head = malloc(sizeof(struct ListNode));
            tail = head;
            tail->val = n % 10;
            tail->next = NULL;
        }
        else {
            tail->next = malloc(sizeof(struct ListNode));
            tail->next->val = n % 10;
            tail = tail->next;
            tail->next = NULL;
        }
        carry = n / 10;

        if (l1)
            l1 = l1->next;
        if (l2)
            l2 = l2->next;
    }
    if (carry > 0) {
        tail->next = malloc(sizeof(struct ListNode));
        tail->next->val = carry;
        tail->next->next = NULL;
    }
    return head;
}

Python3

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        ret = ListNode(0)
        temp = ret
        carry = 0
        while l1 or l2:
            val1 = l1.val if l1 else 0
            val2 = l2.val if l2 else 0
            val = val1 + val2 + carry
            carry = val // 10

            temp.next = ListNode(val % 10)
            temp = temp.next

            if l1: l1 = l1.next
            if l2: l2 = l2.next

        if carry > 0:
            temp.next = ListNode(carry)

        return ret.next

时间复杂度： \(O(max(m,n))\) , m, n 为两个链表的长度
空间复杂度： \(O(max(m,n))\)