LeetCode2_ Add two numbers

Original article , Reprint please indicate the source .

Topic type ： secondary

The title is as follows

Here are two for you Non empty The linked list of , Represents two nonnegative integers . Each of them is based on The reverse Stored in , And each node can only store a Numbers .
Please add up the two numbers , And returns a linked list representing sum in the same form .
You can assume that in addition to the numbers 0 outside , Neither of these numbers 0 start .

Example 1：

 Input ：l1 = [2,4,3], l2 = [5,6,4]
 Output ：[7,0,8]
 explain ：342 + 465 = 807.

Example 2：

 Input ：l1 = [0], l2 = [0]
 Output ：[0]

Example 3：

 Input ：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
 Output ：[8,9,9,9,0,0,0,1]

Tips ：

 The number of nodes in each list is in the range  [1, 100]  Inside 
0 <= Node.val <= 9
 The title data guarantees that the number indicated in the list does not contain leading zeros 

solution

Simple and easy to understand , Non recursive version

Complexity analysis
Time complexity ：O(max(m,n)) , among m and n They are the length of two linked lists . We need to traverse all the positions of the two linked lists , And processing each location only requires O(1) Time for .
Spatial complexity ：O(1). Note that the return value is not included in the spatial complexity .

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */
class Solution {
    
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    
        ListNode* pRoot = new ListNode(0);
        ListNode* pCursor = pRoot;
        int nCarry = 0;
        while(l1 || l2 || nCarry > 0)
        {
    
            int l1Value = l1?l1->val:0;
            int l2Value = l2?l2->val:0;
            int nSum = l1Value+l2Value+nCarry;
            nCarry = nSum/10;

            ListNode* pNext = new ListNode(nSum%10);
            pCursor->next = pNext;
            pCursor = pNext;

            if(l1)
                l1 = l1->next;
            if(l2)
                l2 = l2->next;
        }

        return pRoot->next;
    }
};

leetcode score

thank you , It's not easy to create , Great Xia, please stay … Move your lovely hands , Give me a compliment before you go <(￣︶￣)>