Leetcode 2: Add Two Numbers - Cse Nerd Leetcode Detailed Solutions

Category: Medium

Problem

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.

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

Examples

Example 1:

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

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]

1 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]

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

Solution Approach

In this problem of adding two numbers, we have to add 2 numbers but they are in linked list form. The numbers are stored in reverse order in the linked list hence the last digit of the number is the first node and so on.

The approach is very straight forward as the numbers are already reversed so we just have to check the carry-over possibility. We might have to add extra nodes in case of any carryovers in the last digit. We have to iterate through both the lists in parallel and add the corresponding values and if the value exceeds 9 then we have to make one new node to incorporate this carrying value. In the end, we just return the new linked list with the sum. This approach will have a time complexity of O(n) as we are iterating through both the links in parallel and extra space is required to store the returning list hence the space complexity will be O(n).

Coming to the code part of the solution, we create a head node and we set that head node as the current node. We also initialize a variable called sum which will store the intermediate sum. Then we iterate through the lists together in parallel. We first divide the sum by 10 so in case if the previous carry was left that can be incorporated in the current sum. Then we check one by one whether the node’s value is not null and if it is so we add the value of the node to the sum and similarly we do the same process for the other list’s node also. After that, we create a node and store it in the next node of the current node and whose value will be the sum’s value modulo 10 so that only one digit is stored in that node.

Next, we just point to the next node. After the two lists have been iterated through, we still have to check that if extra carry is present or not and if it is present then we just add one more node with a value of 1. In the end, we just return the next node of the head as the answer.

Solution code

class Solution {
  public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode head = new ListNode(-1);
    ListNode current = head;
    int sum = 0;
    while(l1!=null || l2!=null){
      sum /= 10;
      if(l1!=null){
        sum+=l1.val;
        l1 = l1.next;
      }
      if(l2!=null){
        sum+=l2.val;
        l2 = l2.next;
      }
      current.next = new ListNode(sum%10);
      current = current.next;
    }
    if(sum >= 10){
      current.next = new ListNode(1);
    }
    return head.next;
  }
}

class Solution {

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

ListNode head = new ListNode(-1);

ListNode current = head;

int sum = 0;

while(l1!=null || l2!=null){

sum /= 10;

if(l1!=null){

sum+=l1.val;

l1 = l1.next;

}

if(l2!=null){

sum+=l2.val;

l2 = l2.next;

}

current.next = new ListNode(sum%10);

current = current.next;

}

if(sum >= 10){

current.next = new ListNode(1);

}

return head.next;

}

For more Leetcode explained solutions visit Leetcode Solutions. If you like capture the flag challenges visit here.

Check out my socials below in the footer. Feel free to ask any doubts in the comment section or contact me via Contact page I will surely respond. Happy Leetcoding