快捷導(dǎo)航

C++實現(xiàn)算法兩個數(shù)字相加詳解

更新時間：2021年07月09日 09:35:48 作者：Grandyang

這篇文章主要介紹了C++實現(xiàn)算法兩個數(shù)字相加詳解,本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下

Add Two Numbers 兩個數(shù)字相加

You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1's digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.
EXAMPLE
Input: (7-> 1 -> 6) + (5 -> 9 -> 2).That is, 617 + 295.
Output: 2 -> 1 -> 9.That is, 912.
FOLLOW UP
Suppose the digits are stored in forward order. Repeat the above problem.
EXAMPLE
Input: (6 -> 1 -> 7) + (2 -> 9 -> 5).That is, 617 + 295.
Output: 9 -> 1 -> 2.That is, 912.

LeetCode上的原題，請參考另一篇文檔Add Two Numbers 兩個數(shù)字相加。

跟那道LeetCode有所不同的是，這道題還有個Follow Up，把鏈表存的數(shù)字方向變了，原來是表頭存最低位，現(xiàn)在是表頭存最高位。既然是翻轉(zhuǎn)了鏈表，那么一種直接的解法是把兩個輸入鏈表都各自翻轉(zhuǎn)一下，然后用之前的方法相加完成，再把得到的結(jié)果翻轉(zhuǎn)一次，就是結(jié)果了，翻轉(zhuǎn)鏈表的方法可以參考另一篇文檔Reverse Linked List 倒置鏈表。代碼如下：

解法一：

// Follow up
class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        ListNode *dummy = new ListNode(-1);
        ListNode *cur = dummy;
        int carry = 0;
        l1 = reverseList(l1);
        l2 = reverseList(l2);
        while (l1 || l2) {
            int n1 = l1 ? l1->val : 0;
            int n2 = l2 ? l2->val : 0;
            int sum = n1 + n2 + carry;
            carry = sum / 10;
            cur->next = new ListNode(sum % 10);
            cur = cur->next;
            if (l1) l1 = l1->next;
            if (l2) l2 = l2->next;
        }
        if (carry) cur->next = new ListNode(1);
        return reverseList(dummy->next);
    }
    ListNode *reverseList(ListNode *head) {
        if (!head) return head;
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;
        ListNode *cur = head;
        while (cur->next) {
            ListNode *tmp = cur->next;
            cur->next = tmp->next;
            tmp->next = dummy->next;
            dummy->next = tmp;
        }
        return dummy->next;
    }
};

如果我們不采用翻轉(zhuǎn)鏈表的方法該怎么做呢，這就比較復(fù)雜了。首先我們要縣分別計算出兩個鏈表的長度，然后給稍短一點的鏈表前面補0，補到和另一個鏈表相同的長度。由于要從低位開始相加，而低位是鏈表的末尾，所以我們采用遞歸來處理，先遍歷到鏈表的末尾，然后從后面相加，進位標示符carry用的是引用，這樣保證了再遞歸回溯時值可以正確傳遞，每次計算的節(jié)點后面接上上一次回溯的節(jié)點，直到回到首節(jié)點完成遞歸。最后還是處理最高位的進位問題。代碼如下：

解法二：

// Follow up
class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        int n1 = 0, n2 = 0, carry = 0;;
        n1 = getLength(l1);
        n2 = getLength(l2);
        if (n1 > n2) l2 = padList(l2, n1 - n2);
        if (n2 > n1) l1 = padList(l1, n2 - n1);
        ListNode *res = addTwoNumbersDFS(l1, l2, carry);
        if (carry == 1) {
            ListNode *tmp = new ListNode(1);
            tmp->next = res;
            res = tmp;
        }
        return res;
    }
    ListNode *addTwoNumbersDFS(ListNode *l1, ListNode *l2, int &carry) {
        if (!l1 && !l2) return NULL;
        ListNode *list = addTwoNumbersDFS(l1->next, l2->next, carry);
        int sum = l1->val + l2->val + carry;
        ListNode *res = new ListNode(sum % 10);
        res->next = list;
        carry = sum / 10;
        return res;
    }
    ListNode *padList(ListNode *list, int len) {
        ListNode *dummy = new ListNode(-1);
        ListNode *cur = dummy;
        for (int i = 0; i < len; ++i) {
            cur->next = new ListNode(0);
            cur = cur->next;
        }
        cur->next = list;
        return dummy->next;
    }
    int getLength(ListNode *list) {
        ListNode *cur = list;
        int res = 0;
        while (cur) {
            ++res;
            cur = cur->next;
        }
        return res;
    }
};

到此這篇關(guān)于C++實現(xiàn)算法兩個數(shù)字相加詳解的文章就介紹到這了,更多相關(guān)C++實現(xiàn)兩個數(shù)字相加內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: