Linked Lists Questions: Add Two Numbers as LinkedList

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 Analys…

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



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



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.


Print Share Comment Cite Upload Translate
APA
Kathan Vakharia | Sciencx (2024-03-29T07:01:11+00:00) » Linked Lists Questions: Add Two Numbers as LinkedList. Retrieved from https://www.scien.cx/2021/06/26/linked-lists-questions-add-two-numbers-as-linkedlist/.
MLA
" » Linked Lists Questions: Add Two Numbers as LinkedList." Kathan Vakharia | Sciencx - Saturday June 26, 2021, https://www.scien.cx/2021/06/26/linked-lists-questions-add-two-numbers-as-linkedlist/
HARVARD
Kathan Vakharia | Sciencx Saturday June 26, 2021 » Linked Lists Questions: Add Two Numbers as LinkedList., viewed 2024-03-29T07:01:11+00:00,<https://www.scien.cx/2021/06/26/linked-lists-questions-add-two-numbers-as-linkedlist/>
VANCOUVER
Kathan Vakharia | Sciencx - » Linked Lists Questions: Add Two Numbers as LinkedList. [Internet]. [Accessed 2024-03-29T07:01:11+00:00]. Available from: https://www.scien.cx/2021/06/26/linked-lists-questions-add-two-numbers-as-linkedlist/
CHICAGO
" » Linked Lists Questions: Add Two Numbers as LinkedList." Kathan Vakharia | Sciencx - Accessed 2024-03-29T07:01:11+00:00. https://www.scien.cx/2021/06/26/linked-lists-questions-add-two-numbers-as-linkedlist/
IEEE
" » Linked Lists Questions: Add Two Numbers as LinkedList." Kathan Vakharia | Sciencx [Online]. Available: https://www.scien.cx/2021/06/26/linked-lists-questions-add-two-numbers-as-linkedlist/. [Accessed: 2024-03-29T07:01:11+00:00]
rf:citation
» Linked Lists Questions: Add Two Numbers as LinkedList | Kathan Vakharia | Sciencx | https://www.scien.cx/2021/06/26/linked-lists-questions-add-two-numbers-as-linkedlist/ | 2024-03-29T07:01:11+00:00
https://github.com/addpipe/simple-recorderjs-demo