2.Add Two Numbers [M]

题目:

You are given two linked lists representing two non-negative numbers. 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.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8

思路:

题目的大意是两个链表求和,和也是一个链表(链表是逆序存的数字) 这和大数的加减很像,不过这个进位是从后向前。 所以可以同时从前往后加,然后保留进位。

其实做这种大数加减的题目不管是用的大数组还是链表,都是一样的:

  • 首先做个大循环,对每一位进行操作:

    • 当前位:(A[i]+B[i])%10
    • 进位:(A[i]+B[i])/10

这里要注意一点,就是可能两个数组不是同样的长度,需要考虑一个数组已经到头,另一个数组还没结束的情况

代码

我的这个代码写的不够好,考虑的过于复杂,可以直接看下面更精巧的代码。

/**
 * 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) {
        //异常判断
        if(l1 == NULL && l2 == NULL)
            return NULL;
        if(l1 == NULL)
            return l2;
        if(l2 == NULL)
            return l1;  
        //初始化
        ListNode * result = new ListNode((l1->val + l2->val)%10);
        int carry = (l1->val + l2->val)/10;  //表示进位
        ListNode* templ1 = l1;
        ListNode* templ2 = l2;
        ListNode* tempresult = result;
        //这里弄一个结束节点,有利于当一个节点到结尾后做操作
        ListNode* EndNode = new ListNode(0);
        while(templ1->next != NULL || templ2->next != NULL)
        {
            //如果某个链表已经到结尾了,那么就把它变成EndNode,特点是值为0,next = NULL
            if(templ1->next == NULL)
                templ1 = EndNode;
            else
                templ1 = templ1->next;
            if(templ2->next == NULL)
                templ2 = EndNode;
            else
                templ2 = templ2->next; 
            tempresult->next = new ListNode((templ1->val + templ2->val + carry)%10);            
            carry = (templ1->val + templ2->val + carry)/10;

            tempresult = tempresult->next;

        }
        if(carry == 1)
            tempresult->next = new ListNode(1);
        return result;

    }
};

更精巧的代码

不得不说,potpie的这个代码比我上面的代码精简了不少,我上面的代码考虑的太多了,因为我通式用的templ1->val + templ2->val + carry,导致每次需要对先结束的链表进行尾部填充,而且开头多了很多额外的代码。

他的代码,2个链表是独立操作的,而且代码写的很精简,基本没废话!赞

public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode c1 = l1;
        ListNode c2 = l2;
        ListNode sentinel = new ListNode(0);
        ListNode d = sentinel;
        int sum = 0;
        while (c1 != null || c2 != null) {
            sum /= 10;
            if (c1 != null) {
                sum += c1.val;
                c1 = c1.next;
            }
            if (c2 != null) {
                sum += c2.val;
                c2 = c2.next;
            }
            d.next = new ListNode(sum % 10);
            d = d.next;
        }
        if (sum / 10 == 1)
            d.next = new ListNode(1);
        return sentinel.next;
    }
}

results matching ""

    No results matching ""