題目概要

完成兩個(gè)鏈表的“加法”并返回存儲(chǔ)“和”的鏈表。

題目鏈接

Add Two Numbers

解題思路

1. 迭代兩個(gè)鏈表，逐位相加
2. 相加過(guò)程中考慮進(jìn)位
3. 注意兩個(gè)鏈表不想等長(zhǎng)度下，對(duì)長(zhǎng)鏈表的處理

復(fù)雜度分析

時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：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;
    }
};

廣告區(qū)域

本人和小伙伴們承接各種軟件項(xiàng)目，有需求的可以聯(lián)系我們。
QQ: 2992073083