神奇补0解决链表相加：LeeCode002两数相加

题目描述

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

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

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

解法一：暴力计算

该解法使用数字相加的方法进行计算，但该解法有一个致命的问题是整数溢出。所以，严格意义上说，这种方式是错误的。代码如下：

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

int listNodeLength(ListNode *list) {
    if (list == NULL || list->next == NULL)
    {
        return 0;
    }
    
    int size = 0;
    ListNode *tmpPoint = list;
    while(tmpPoint->next != NULL) {
        size++;
        tmpPoint = tmpPoint->next;
    }
    return size;
}


class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int sum1 = getListSum(l1);
        int sum2 = getListSum(l2);
        int sum3 = sum1 + sum2;
        
        int sum3Length = 0;
        int tmp = sum3;
        while(tmp > 0) {
            tmp = tmp/10;
            sum3Length++;
        }
        
        ListNode *head = NULL;
        ListNode *tail = nullptr;
        int m = sum3;
        while(sum3Length > 0) {
            int val = m%(10);
            m = m / 10;
            
            ListNode *list = new ListNode(val);
            if (head)
            {
                tail->next = list;
                tail = list;
            } else {
                head = list;
                tail = head;
            }
            sum3Length--;
        }
        return head;
        
    }
    
    int getListSum(ListNode *list) {
        int length = listNodeLength(list);
        
        int sum = 0;
        int index = 0;
        ListNode *tmpPoint = list;
        while(tmpPoint != NULL) {
            sum += pow(10, length-index) * tmpPoint->val;
            tmpPoint = tmpPoint->next;
            index++;
        }
        
        return sum;
        
    }
};

解法二：按位计算

该解法使用一个变量表示进位值。如下图，temp表示进位。将两个list长度改为一致，通过补0操作。

具体代码如下：

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

int listNodeLength(ListNode *list) {
    if (list == NULL)
    {
        return 0;
    }
    
    int size = 0;
    ListNode *tmpPoint = list;
    while(tmpPoint != NULL) {
        size++;
        tmpPoint = tmpPoint->next;
    }
    return size;
}


class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int l1Length = listNodeLength(l1);
        int l2Length = listNodeLength(l2);
        
        int max = l1Length;
        ListNode *maxListNode = l1;
        int min = l2Length;
        ListNode *minListNode = l2;
        if (l1Length<l2Length)
        {
            max = l2Length;
            maxListNode = l2;
            
            min = l1Length;
            minListNode = l1;
        }
        
        ListNode *minTail = minListNode;
        ListNode *maxTail = maxListNode;
        while (maxTail != NULL) {
            if (minTail -> next == NULL) {
                minTail->next = new ListNode(0);
            }
            maxTail = maxTail -> next;
            minTail = minTail->next;
        }
        
        int temp = 0;
        ListNode* l1temp = minListNode;
        ListNode* l2temp = maxListNode;
        ListNode *result = NULL;
        ListNode *resultTail = NULL;
        for (int i = 0; i < max; ++i)
        {
            int sum = l1temp->val + l2temp->val + temp;
            temp = sum/10;
            int val = sum%10;
            ListNode *node = new ListNode(val);
            if (result == NULL)
            {
                result = node;
                resultTail = result;
            }
            else
            {
                resultTail->next = node;
                resultTail = node;
            }
            
            l1temp = l1temp->next;
            l2temp = l2temp->next;
        }
        
        if (temp > 0) {
            resultTail->next = new ListNode(temp);
        }
        return result;
    }
};

源码

你可以通过点击这里获取源代码：LeeCodeTrain

讨论

关于没到题目的解法我都发布在我的博客：riverli.me 和我的微信公众号。

欢迎你关注我的公众号，一起讨论：算法、前端、iOS、Android、用户体验、架构、程序员发展等内容。