Add Two Numbers

题目意思:给你两个非空链表,分别代表两个数.链表中每个结点存放一个数位,其顺序和对应的数顺序是相反的. 将这两个数相加,然后返回一个代表该数的链表.

Solution

#include <iostream>
using namespace std;
struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x):val(x),next(NULL){}
};
class Solution
{
public:
    ListNode* addTwoNumbers(ListNode* LA, ListNode* LB)
    {
        int carry = 0; //前面传来的进位
        ListNode *LC = new ListNode(0);
        ListNode *p = LC;
        while(LA && LB)
        {
            int sum = LA->val + LB->val + carry;
            //取低位
            p->val = sum % 10;
            //取进位
            carry = sum / 10;
            //如果下一次循环两个链表都没有走到尽头,则分配下一个节点
            if(LA->next && LB->next)
            {
                ListNode *node = new ListNode(0);
                p->next = node;
                p = node;
            }
            LA = LA->next;
            LB = LB->next;
        }
        //下面的两个while最多只有一个会执行
        while(LA)
        {
            ListNode *node = new ListNode(0);
            node->val = (LA->val + carry) % 10;
            carry = (LA->val + carry) / 10;
            p->next = node; p = node;
            LA = LA->next;
        }
        while(LB)
        {
            ListNode *node = new ListNode(0);
            node->val = (LB->val + carry) % 10;
            carry = (LB->val + carry) / 10;
            p->next = node; p = node;
            LB = LB->next;
        }
        //如果所有元素都处理完,仍有进位,那么该位为最高位
        if(carry)
        {
            ListNode *node = new ListNode(0);
            node->val = carry;
            p->next = node;
        }
        return LC;
    }
    //从数组创建链表
    ListNode *CreateList(int* arr,int n)
    {
        ListNode *L = new ListNode(0);
        ListNode *p = L;
        for(int i = 0;i < n;++i)
        {
            p->val = arr[i];
            if(i+1 == n) continue;
            ListNode *node = new ListNode(0);
            p->next = node;
            p = node;
        }
        return L;
    }
    //打印链表
    void PrintList(ListNode* L)
    {
        while(L)
        {
            cout<<L->val;
            if(L->next) cout<<"->";
            L = L->next;
        }
        cout<<endl;
    }
};
//=======================Driver===========================
int main()
{
    int la[] = {5};
    int lb[] = {5};
    Solution s;
    ListNode *LA = s.CreateList(la,sizeof(la)/sizeof(int)); s.PrintList(LA);
    ListNode *LB = s.CreateList(lb,sizeof(lb)/sizeof(int)); s.PrintList(LB);
    ListNode *LC=s.addTwoNumbers(LA,LB); s.PrintList(LC);
    return 0;
}


/*
===========complexity==============
记链表LA,LB的长度分别是m,n:
Time Complexity:O(max(m,,n))
Space Complexity:O(max(m,n))
===========makefile=================
all:
    @g++  solve.cpp -o   solve
    @./solve
clean:
    rm -f solve
    reset
===========leetcode accepted========
1562 / 1562 test cases passed.
Status: Accepted
Runtime: 33 ms
Submitted: 0 minutes ago
===========submission date=========
2017-01-07 Sat 01:14 PM
*/

Analysis

这道题由于链表本身就是逆序的,很容易进行运算.同时遍历两个链表LA,LB并维护一个进位变量carry, 依次地将相应结点相加,放到结果链表LC中即可.

这道题在实际编写代码的时候,有以下几点需要我们注意:

• 两个链表同时遍历并新建结果链表结点的技术处理,自己写一下代码就知道难点在哪里了.我这里的处理是, 在同时遍历开始之前就生成一个结点,在循环内部,生成的新结点都是供下一次循环所有,但可能下一次循环就直接结束了, 因此循环内生产新结点时,先判断下一次循环是否结束,如果结束就不生成结点,否则生成结点供下一次使用.
• 每一次两个结点相加的结果取高低位:这个应该没什么难的,两个数位相加,范围为0~18,所以对于任意数位和sum, 取低位sum%10放入LC结点中,取高位sum/10放入进位carry中
• 很容易忽略的一点是,最后的进位处理,比如说789+453=2421,前面三位处理后,链表为2->4->2,最后处理的是7+4+carry(1),新生成的进位是1,这时候两个数字的所有数值位都处理完了, 应该将进位1放到最后面才算完成,如果忽略这一点,将会输出2->4->2,而实际应是2->4->2->1.