欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Leetcode--Add Two Numbers(0002)

程序员文章站 2022-05-05 09:36:26
转载请注明:http://www.cnblogs.com/igoslly/p/8672467.html 来看一下题目: You are given two non-empty linked lists representing two non-negative integers. The digit ......

转载请注明: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;  
    }
};