Leetcode--Add Two Numbers(0002),

2019-11-09 作者:计算机知识   |   浏览(87)

Leetcode--Add Two Numbers(0002),

转载请注明:

 

来看一下题目:

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;  
    }
};

 

Two Numbers(0002), 转载请注明: 来看一下题目: You are given two non-empty linked lists representing two n...

从今天开始,写一下我在刷 LeetCode 时的心得体会,包括自己的思路和别人的优秀思路,欢迎各种监督啊! 2016/10/9
编程语言是 Java,代码托管在我的 GitHub 上,包括测试用例。欢迎各种批评指正!

<br />

本文由大发体育发布于计算机知识,转载请注明出处:Leetcode--Add Two Numbers(0002),

关键词: