首页 > > 程序设计 > C/C++ >

Leetcode--Add Two Numbers(0002)

2018-06-17 20:55:32来源：未知阅读 ()

转载请注明：http://www.cnblogs.com/igoslly/p/8672467.html

来看一下题目：

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

题目意思其实就是将两个数，以链表逆序的方式进行存储

求和后，将结果也逆序输出

思路：

1、由于两个数的大小位数，链表 -> int数进行的想法基本无望，可能越界

2、链表已经逆序，已经提供很好的“对应位相加，向前进位”的运算模式

注意点：

1、List1和List2不等长

2、当某个List完成后，可单个计算另外的List

3、考虑进位关系，例如9+99999

4、最后进位时，需额外设定val=1的结点

实现方法1（初始）：

方法1即是依照上面思路，依样画葫芦得到的结果

但其实细看，本题代码重复的部分太多，而且一直需要使用pre变量跟踪前结点，有些多余

/**
 * 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) {
        ListNode *p1=l1,*p2=l2,*pre=p1;
        int up=0;
        
        // 将结点l1作为结果链表返回，在l1和l2均在有效范围内，进行添加，同时更新up进位
        while(p1&&p2){
            p1->val+=p2->val+up;
            up=p1->val/10;
            if(up==1){
                p1->val-=10;
            }
            pre=p1;
            p1=p1->next;
            p2=p2->next;
        }
        
        // 当l1结束后，pre最后个元素连接到l2后部
        if(p1==NULL){
            pre->next=p2;
            while(p2!=NULL){
                p2->val+=up;
                up=p2->val/10;
                if(up==1){
                    p2->val-=10;
                }
                pre=p2;
                p2=p2->next;
            }
        }
        
        // 当l2结束后，单独计算l1
        if(p2==NULL){
            while(p1!=NULL){
                p1->val+=up;
                up=p1->val/10;
                if(up==1){
                    p1->val-=10;
                }
                pre=p1;
                p1=p1->next;
            }
        }
        
        // 当计算结束，up=1时，表示和多一位，新创建val=1的ListNode添加
        if(up==1){
            pre->next=new ListNode(1);
        }
        return l1;
    }
};

实现方法2 （对方法1进行优化）：

相对看起来更加简洁

/**
 * 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) {  
        int carry=0;
        ListNode* listNode=new ListNode(0);
        ListNode* p1=l1,*p2=l2,*p3=listNode;
        
        // 修改判断条件从 && 到 ||
        while(p1!=NULL||p2!=NULL)
        {   
            // 在while循环里添加p1和p2的判断，省去了某个List完毕后单独List的情况
            if(p1!=NULL)
            {
                carry+=p1->val;
                p1=p1->next;
            }
            if(p2!=NULL)
            {
                carry+=p2->val;
                p2=p2->next;
            }
            p3->next=new ListNode(carry%10);
            p3=p3->next;
            carry/=10;
        }
        
        // 由于辟出了单独的result链表，故而无需再用pre继续前结点
        if(carry==1)
            p3->next=new ListNode(1);
        return listNode->next;  
    }
};