Leetcode0002--Add Two Numbers 链表求和

【转载请注明】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=;

        // 将结点l1作为结果链表返回，在l1和l2均在有效范围内，进行添加，同时更新up进位

        while(p1&&p2){

            p1->val+=p2->val+up;

            up=p1->val/;

            if(up==){

                p1->val-=;

            }

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

                if(up==){

                    p2->val-=;

                }

                pre=p2;

                p2=p2->next;

            }

        }

        // 当l2结束后，单独计算l1

        if(p2==NULL){

            while(p1!=NULL){

                p1->val+=up;

                up=p1->val/;

                if(up==){

                    p1->val-=;

                }

                pre=p1;

                p1=p1->next;

            }

        }

        // 当计算结束，up=1时，表示和多一位，新创建val=1的ListNode添加

        if(up==){

            pre->next=new ListNode();

        }

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

        ListNode* listNode=new ListNode();

        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%);

            p3=p3->next;

            carry/=;

        }

        // 由于辟出了单独的result链表，故而无需再用pre继续前结点

        if(carry==)

            p3->next=new ListNode();

        return listNode->next;

    }

};

巴特西

Leetcode0002--Add Two Numbers 链表求和

最新文章

热门文章