LeetCode2:Add Two Numbers

一时失言乱红尘 2022-08-20 07:29 132阅读 0赞

原题链接：[传送门][Link 1]

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

原题大意：

给两个链表，表示两个数，要求按照数学的方式加起来，注意这里的数字是倒序的，也就是说进位要进到下一位。

这里我们需要线性遍历这两个链表，取出相应节点的数字，同时新建节点，进行计算。需要注意的地方是，两个链表的长度不一定相同，左面对齐，需要判断当前节点是否为空。代码如下：

/**
     * 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) {
            //用carry表示进位
            int carry=0;
            ListNode* head=new ListNode(0);
            ListNode* curr=head;
            while(l1||l2)
            {
                int val1=0;
                if(l1)
                {
                    val1=l1->val;
                    l1=l1->next;
                }
                int val2=0;
                if(l2)
                {
                    val2=l2->val;
                    l2=l2->next;
                }
                int digit=val1+val2+carry;
                carry=digit/10;
                curr->next=new ListNode(digit%10);
                curr=curr->next;
            }
            //如果还有进位，就新加一个节点
            if(carry)
            {
                curr->next=new ListNode(1);
            }
            return head->next;
        }
    };

[Link 1]: https://leetcode.com/problems/add-two-numbers/