LinkedList Questions: Add Two Numbers as Linked List

In this series of posts, I will discuss coding questions on the LinkedList Data structure.
The posts in this series will be organized in the following way,

Question Link ❓

Possible Explanation 📝

Documented C++ Code 🧹

Time and Space Complexity Analysis ⌛🌌

The Question

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.

💡 Give yourself atleast 15-20 mins to figure out the solution :)

Explanation

Visualize how you used to do addition in your elementary school.

First create a dummynode whose next pointer will hold our resulting linkedlist. Make a temp pointer point to it. (it will be used for appending the resulting nodes)

📒 The resulting linkedlist is also in reversed order

Then iterate through both the list, untill we reach the end in both the lists and there's no carry left.

At every iteration, perform the arithmetic that we do while adding digits and calculate the resulting digit.

Create a newnode with value of resulting digit and append it to the end of our resulting linkedlist. (Notice the usecase of modulo operator).

C++ Code

Definition of LinkedList

//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) {}
};

Solution

#include <bits/stdc++.h>
#include "../linkedlist.h"
using namespace std;

/*
-Time:O(max(n1, n2))
-Space:O(max(n1,n2))
*/
class Solution
{
public:
    //! Here we have to return the reversed list only
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
    {

        ListNode *start = new ListNode();
        ListNode *temp = start;

        //starting carry is zero
        int carry = 0;

        //go through both lists and create a new node untill
        //nodes exist in any of the lists or carry is 1
        while (l1 != nullptr || l2 != nullptr || carry != 0)
        {

            int sum = 0;

            if (l1 != nullptr)
            {
                sum += l1->val;
                l1 = l1->next;
            }

            if (l2 != nullptr)
            {
                sum += l2->val;
                l2 = l2->next;
            }

            sum = sum + carry;
            carry = sum / 10; //updating carry for next digit sum

            //note: We take modulo with 10
            temp->next = new ListNode(sum % 10);
            temp = temp->next;
        }

        return start->next;
    }
};