93. Add two numbers in Linked List

Given two non-empty linked lists linkedList1 and linkedList2 which represent two non-negative integers.

The digits are stored in reverse order with each node storing one digit.

Add two numbers and return the sum as a linked list.

  • The sum Linked List will be in reverse order as well.
  • The Two given Linked Lists represent numbers without any leading zeros, except when the number is zero itself.

Example 1:

Input: linkedList1 = [5, 4], linkedList2 = [4]

Output: [9, 4]

Explanation: linkedList1 = 45, linkedList2 = 4.

linkedList1 + linkedList2 = 45 + 4 = 49.

The sum is 49 and when prepare the linked list we reverse the number [9, 4]

Example 2:

Input: linkedList1 = [4, 5, 6], linkedList2 = [1, 2, 3]

Output: [5, 7, 9]

Explanation: linkedList1 = 654, linkedList2 = 321.

linkedList1 + linkedList2 = 654 + 321 = 975.

The sum is 975 and when prepare the linked list we reverse the number [5, 7, 9]The sum

Now Your Turn!

Pick the correct output for the given input

Input: linkedList1 = [1], linkedList2 = [8, 7]

Still unsure what the problem is asking ?

Let’s go through a few more examples, step by step, to make it clearer.

Constraints:

  • 1 <= Number of nodes in each Linked List <= 100
  • 0 <= value of each node in both Linked List <= 9
  • It is guaranteed that the list represents a number that does not have leading zeros.

Hints

Frequently Occurring Doubts

Interview Follow-up Questions

Fun Facts

0
/*
Definition of singly linked list:
class ListNode{
public:
int data;
ListNode *next;
ListNode() : data(0), next(nullptr) {}
ListNode(int x) : data(x), next(nullptr) {}
ListNode(int x, ListNode *next) : data(x), next(next) {}
};
*/
 
class Solution {
public:
ListNode* addTwoNumbers(ListNode* &linkedList1, ListNode* &linkedList2) {
//your code goes here
}
};
Test Case

Input:

Linked List1
Linked List2
to save your code