【LeetCode】2. 两数相加

题目链接

Python3

方法： 模拟 $⟮O(n)、O(1)⟯$

# 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(None)
        carry = 0
        while l1 or l2:
            carry += (l1.val if l1 else 0) + (l2.val if l2 else 0 )
            cur.next = ListNode(carry % 10)  # 注意这里
            carry = carry // 10
            
            cur = cur.next 
            if l1: l1 = l1.next 
            if l2: l2 = l2.next

        if carry > 0:  # 处理 最后一个进位
            cur.next = ListNode(carry) 

        return dummy.next 

C++

/**
 * 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) {
        ListNode *dummy = new ListNode(0);  // 虚拟结点 定义
        ListNode* cur = dummy;
        int carry = 0;
        while (l1 || l2){
            int n1 = l1 ? l1->val : 0;
            int n2 = l2 ? l2->val : 0;
            int total = n1 + n2 + carry;
            cur->next = new ListNode(total % 10);
            carry = total / 10;
            
            cur = cur->next;
            if (l1){
                l1 = l1->next;
            }
            if (l2){
                l2 = l2->next;
            }
        }
        if (carry > 0){
            cur->next = new ListNode(carry);
        }
        return dummy->next;
    }
};