DEV Community

Cover image for LinkedList Questions: Add Two Numbers as Linked List
Kathan Vakharia
Kathan Vakharia

Posted on • Updated on

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,

  1. Question Link ❓
  2. Possible Explanation πŸ“
  3. Documented C++ Code 🧹
  4. 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.

https://leetcode.com/problems/add-two-numbers/#

πŸ’‘ 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) {}
};
Enter fullscreen mode Exit fullscreen mode

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;
    }
};

Enter fullscreen mode Exit fullscreen mode

Complexity Analysis

n1 and n2 are sizes of given linkedlists.

Time Complexity: O(max(n1, n2))

Since we have to travel both the lists completely.

Space Complexity: O(max(n1, n2))

Same reason as above.

πŸ”Concretely both complexities will be O(max(n1, n2) + 1) by taking the end-carry into account but asymptotically, it doesn't matter.

Top comments (0)