logo
logo

Add Two Numbers As Reversed Linked Lists

Lesson

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order, and each node of the linked lists contains a single digit. Add the two numbers and return the sum as a linked list.

Write a function that takes in two linked lists representing non-negative numbers, and returns a linked list representing the sum of the two numbers.

Example Input:

LinkedList1: 6 -> 7 -> 3
LinkedList2: 8 -> 9 -> 4

Example Output:

LinkedList: 4 -> 7 -> 8

Walkthrough

Solution Explanation

The function 
addTwoNumbers
 takes in two linked lists representing non-negative numbers, and returns a linked list representing the sum of the two numbers. We start by initializing a 
result
 linked list and a 
current
 node that points to the 
result
 linked list. We also initialize a 
carry
 variable to keep track of any carryover that we need to add to the next node in the list.We then loop through the linked lists as long as either 
l1
 or 
l2
 has a value, or if there is a carryover. In each iteration, we add the value of the nodes of 
l1
 and 
l2
, as well as the carryover from the previous iteration. If the sum is greater than or equal to 10, we set 
carry
 to 1, otherwise we set it to 0. We then create a new node with the sum modulo 10, which is the single digit that we need to add to the 
result
 linked list. We then set the 
current
 node's 
next
 property to the new node, and move 
current
 to the next node.We then move 
l1
 and 
l2
 to their next nodes, or to 
null
 if they have no more nodes. We continue looping until we reach the end of both linked lists and there is no carryover left.We then return the 
result
 linked list's 
next
 property, which is the actual start of the linked list.

Big O Complexity Analysis:

The time complexity of this function is O(max(m, n)), where 
m
 and 
n
 are the lengths of 
l1
 and 
l2
, respectively. This is because we need to loop through both linked lists, and the number of iterations is determined by the longer of the two linked lists.

The space complexity of this function is O(max(m, n)), because we need to create a new linked list to store the result, and the number of nodes in the linked list is determined by the longer of the two linked lists.

Previous LessonNext Lesson