两数相加

2. 两数相加

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

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

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零

相似题目

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

/** * 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) { } };

cpp 解法, 执行用时: 36 ms, 内存消耗: 69.8 MB, 提交时间: 2023-07-02 10:14:14

/**
 * 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) {
        auto dummy = new ListNode(); // 哨兵节点
        auto cur = dummy;
        int carry = 0; // 进位
        while (l1 || l2 || carry) { // 有一个不是空节点，或者还有进位，就继续迭代
            carry += (l1 ? l1->val : 0) + (l2 ? l2->val : 0); // 节点值和进位加在一起
            cur = cur->next = new ListNode(carry % 10); // 每个节点保存一个数位
            carry /= 10; // 新的进位
            if (l1) l1 = l1->next; // 下一个节点
            if (l2) l2 = l2->next; // 下一个节点
        }
        return dummy->next; // 哨兵节点的下一个节点就是头节点
    }
};

golang 解法, 执行用时: 8 ms, 内存消耗: 4.3 MB, 提交时间: 2023-07-02 10:12:58

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1, l2 *ListNode) *ListNode {
    dummy := &ListNode{} // 哨兵节点
    cur := dummy
    carry := 0 // 进位
    for l1 != nil || l2 != nil || carry != 0 { // 有一个不是空节点，或者还有进位，就继续迭代
        if l1 != nil {
            carry += l1.Val // 节点值和进位加在一起
        }
        if l2 != nil {
            carry += l2.Val // 节点值和进位加在一起
        }
        cur.Next = &ListNode{Val: carry % 10} // 每个节点保存一个数位
        carry /= 10 // 新的进位
        cur = cur.Next // 下一个节点
        if l1 != nil {
            l1 = l1.Next // 下一个节点
        }
        if l2 != nil {
            l2 = l2.Next // 下一个节点
        }
    }
    return dummy.Next // 哨兵节点的下一个节点就是头节点
}

java 解法, 执行用时: 1 ms, 内存消耗: 42.2 MB, 提交时间: 2023-07-02 10:12:44

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(); // 哨兵节点
        ListNode cur = dummy;
        int carry = 0; // 进位
        while (l1 != null || l2 != null || carry != 0) { // 有一个不是空节点，或者还有进位，就继续迭代
            if (l1 != null) carry += l1.val; // 节点值和进位加在一起
            if (l2 != null) carry += l2.val; // 节点值和进位加在一起
            cur = cur.next = new ListNode(carry % 10); // 每个节点保存一个数位
            carry /= 10; // 新的进位
            if (l1 != null) l1 = l1.next; // 下一个节点
            if (l2 != null) l2 = l2.next; // 下一个节点
        }
        return dummy.next; // 哨兵节点的下一个节点就是头节点
    }
}

python3 解法, 执行用时: 64 ms, 内存消耗: 16.1 MB, 提交时间: 2023-07-02 10:12:31

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        cur = dummy = ListNode()  # 哨兵节点
        carry = 0  # 进位
        while l1 or l2 or carry:  # 有一个不是空节点，或者还有进位，就继续迭代
            carry += (l1.val if l1 else 0) + (l2.val if l2 else 0)  # 节点值和进位加在一起
            cur.next = ListNode(carry % 10)  # 每个节点保存一个数位
            carry //= 10  # 新的进位
            cur = cur.next  # 下一个节点
            if l1: l1 = l1.next  # 下一个节点
            if l2: l2 = l2.next  # 下一个节点
        return dummy.next  # 哨兵节点的下一个节点就是头节点

golang 解法, 执行用时: 12 ms, 内存消耗: 4.2 MB, 提交时间: 2023-07-02 10:12:09

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
// l1 和 l2 为当前遍历的节点，carry 为进位
func addTwo(l1, l2 *ListNode, carry int) *ListNode {
    if l1 == nil && l2 == nil { // 递归边界：l1 和 l2 都是空节点
        if carry != 0 {
            return &ListNode{Val: carry} // 如果进位了，就额外创建一个节点
        }
        return nil
    }
    if l1 == nil { // 如果 l1 是空的，那么此时 l2 一定不是空节点
        l1, l2 = l2, l1 // 交换 l1 与 l2，保证 l1 非空，从而简化代码
    }
    carry += l1.Val // 节点值和进位加在一起
    if l2 != nil {
        carry += l2.Val // 节点值和进位加在一起
        l2 = l2.Next // 下一个节点
    }
    l1.Val = carry % 10 // 每个节点保存一个数位
    l1.Next = addTwo(l1.Next, l2, carry/10) // 进位
    return l1
}

func addTwoNumbers(l1, l2 *ListNode) *ListNode {
    return addTwo(l1, l2, 0)
}

java 解法, 执行用时: 1 ms, 内存消耗: 42.2 MB, 提交时间: 2023-07-02 10:11:55

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        return addTwo(l1, l2, 0);
    }

    // l1 和 l2 为当前遍历的节点，carry 为进位
    private ListNode addTwo(ListNode l1, ListNode l2, int carry) {
        if (l1 == null && l2 == null) // 递归边界：l1 和 l2 都是空节点
            return carry != 0 ? new ListNode(carry) : null; // 如果进位了，就额外创建一个节点
        if (l1 == null) { // 如果 l1 是空的，那么此时 l2 一定不是空节点
            l1 = l2;
            l2 = null; // 交换 l1 与 l2，保证 l1 非空，从而简化代码
        }
        carry += l1.val + (l2 != null ? l2.val : 0); // 节点值和进位加在一起
        l1.val = carry % 10; // 每个节点保存一个数位
        l1.next = addTwo(l1.next, (l2 != null ? l2.next : null), carry / 10); // 进位
        return l1;
    }
}

python3 解法, 执行用时: 64 ms, 内存消耗: 16 MB, 提交时间: 2023-07-02 10:11:40

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    # l1 和 l2 为当前遍历的节点，carry 为进位
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode], carry=0) -> Optional[ListNode]:
        if l1 is None and l2 is None:  # 递归边界：l1 和 l2 都是空节点
            return ListNode(carry) if carry else None  # 如果进位了，就额外创建一个节点
        if l1 is None:  # 如果 l1 是空的，那么此时 l2 一定不是空节点
            l1, l2 = l2, l1  # 交换 l1 与 l2，保证 l1 非空，从而简化代码
        carry += l1.val + (l2.val if l2 else 0)  # 节点值和进位加在一起
        l1.val = carry % 10  # 每个节点保存一个数位
        l1.next = self.addTwoNumbers(l1.next, l2.next if l2 else None, carry // 10)  # 进位
        return l1

python3 解法, 执行用时: 60 ms, 内存消耗: 15 MB, 提交时间: 2022-08-26 15:37:48

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        head, tail = None, None
        carry = 0
        while l1 or l2:
            n1, n2 = 0, 0
            if l1:
                n1 = l1.val
                l1 = l1.next
            if l2:
                n2 = l2.val
                l2 = l2.next
            
            v = ( n1 + n2 + carry ) % 10
            carry = ( n1 + n2 + carry ) // 10
            if head == None:
                head = ListNode(v)
                tail = head
            else:
                tail.next = ListNode(v)
                tail = tail.next
        if carry > 0:
            tail.next = ListNode(carry)
        return head

上一题

下一题

详情