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.
LinkedList1: 6 -> 7 -> 3
LinkedList2: 8 -> 9 -> 4
LinkedList: 4 -> 7 -> 8
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
linked list and a
node that points to the
linked list. We also initialize a
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
has a value, or if there is a carryover. In each iteration, we add the value of the nodes of
, as well as the carryover from the previous iteration. If the sum is greater than or equal to 10, we set
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
linked list. We then set the
property to the new node, and move
to the next node.We then move
to their next nodes, or to
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
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
are the lengths of
, 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.