Add Two Numbers

Moderate

0/80

Average time to solve is 20m

Contributed by

181 upvotes

Asked in companies

Problem statement

You are given two non-negative numbers 'num1' and 'num2' represented in the form of linked lists.

The digits in the linked lists are stored in reverse order, i.e. starting from least significant digit (LSD) to the most significant digit (MSD), and each of their nodes contains a single digit.

Calculate the sum of the two numbers and return the head of the sum list.

Example :

Input:
'num1' : 1 -> 2 -> 3 -> NULL
'num2' : 4 -> 5 -> 6 -> NULL

Output: 5 -> 7 -> 9 -> NULL

Explanation: 'num1' represents the number 321 and 'num2' represents 654. Their sum is 975.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains a single integer 'm', the number of elements in 'num1'.
The second line contains 'm' integers, the elements of the first singly linked list / digits of 'num1'.
The third line contains a single integer 'n', the number of elements in 'num2'.
The fourth line contains 'n' integers, the elements of the second singly linked list / digits of 'num2'.

Output Format:

Return the sum linked list.

Note :

You do not need to print anything; it has already been taken care of. Just implement the given function.

Sample Input 1 :

Sample Output 1 :

5 7 9

Explanation for Sample Input 1 :

'num1' represents the number 321 and 'num2' represents 654. Their sum is 975.

Sample Input 2 :

Sample Output 2 :

0 1

Explanation for Sample Input 2 :

'num1' represents 10 and 'num2' represents 0. Their sum is 10.

Sample Input 3 :

Sample Output 3 :

1 0 1

Explanation for Sample Input 3 :

'num1' represents 2 and 'num2' represents 99. Their sum is 101.

Expected Time Complexity :

The expected time complexity is O('m' + 'n').

Constraints :

1 <= 'm', 'n' <= 5 * 10^4
0 <= 'data' in any Linked List node <= 9

The numbers do not contain any leading zeros.
If the number is zero, then there is one node having 'data' = 0.

Time Limit: 1 sec

Console