两数相加(I&II)

两数相加I

题目：链表求和

链表是逆序的，便于直接相加，比如 715 + 352，链表分别是：

5 → 1 → 7

2 → 5 →3

ListNode* addTwoNumbers(ListNode* l1 , ListNode* l2) {
    // 模拟法
    ListNode* head = nullptr;
    ListNode* tail = nullptr;

    int carry = 0;
    // 只要 l1 || l2 还有节点可用
    while (l1 || l2) {
        // l1 || l2 如果为空，节点值视为0
        int n1 = l1 ? l1->val : 0;
        int n2 = l2 ? l2->val : 0;
        // 计算节点和 + 进位
        int sum = n1  + n2 + carry;
        // 创建新节点
        if (head == nullptr) {
            head = new ListNode(sum % 10);
            tail = head;
        } else {
            tail->next = new ListNode(sum % 10);
            tail = tail->next;
        }
        // 计算进位
        carry = sum / 10;
        // 更新节点位置
        if (l1) l1 = l1->next;
        if (l2) l2 = l2->next;
    }
    // 边界情况
    if (carry > 0) {
        tail->next = new ListNode(carry);
    }
    return head;
}

两数相加II

链表是正序的，要反转处理，比如 715 + 352，链表分别是：

7 → 1 → 5

3 → 5 → 2

ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
    l1 = reverse(l1);
    l2 = reverse(l2);

    ListNode *head = nullptr;
    ListNode *tail = nullptr;
    int carry = 0;
    while (l1 || l2) {
        int n1 = l1 ? l1->val : 0;
        int n2 = l2 ? l2->val : 0;
        int sum = n1 + n2 + carry;

        if (head == nullptr) {
            head = new ListNode(sum % 10);
            tail = head;
        } else {
            tail->next = new ListNode(sum % 10);
            tail = tail->next;
        }
        carry = sum / 10;

        if (l1) l1 = l1->next;
        if (l2) l2 = l2->next;
    }
    if (carry > 0) {
        tail->next = new ListNode(carry);
    }
    // 结果也需要反转回来
    return reverse(head);
}

ListNode *reverse(ListNode *head) {
    ListNode *pre = nullptr;
    ListNode *cur = head;
    while (cur != nullptr) {
        ListNode *nxt = cur->next;
        cur->next = pre;
        pre = cur;
        cur = nxt;
    }
    return pre;
}