Add two numbers represented by linked lists

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 contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

 

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 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]




c++ implementation:

struct Node* addTwoLists(struct Node* l1, struct Node* l2)
    {          
         Node* head=new Node(1);
         Node* temp=head;
        int carry=0;
        while(l1!=NULL || l2!=NULL || carry)
        {
            int sum=0;
            if(l1!=NULL)
            {
                sum=sum+l1->data;
                l1=l1->next;
            }
            if(l2!=NULL)
            {
                sum=sum+l2->data;
                l2=l2->next;
            }
            sum=sum+carry;
            carry=sum/10;
            Node* node=new Node(sum%10);
            temp->next=node;
            temp=temp->next;
        }
       return head->next;
         
    }


 Time Complexity: O(N+M)
Space ComplexityO(Max(N,M))
darkmode