Introduction
Linked lists are one of the frequently asked data structures in interviews. Some of the questions on the linked list asked in product-based companies like Amazon, Microsoft are Detect And Remove Cycle, Merge two sorted linked lists, etc.
This blog will discuss the interview problem: add two numbers represented by a linked list previously asked in companies like Amazon, Flipkart, Microsoft, Morgan Stanley, etc. This blog requires a thorough understanding of Linked List so, please go through the blog A Brief Introduction To Linked Lists for a better understanding.
Problem Statement
Two numbers are represented by two linked lists. Write a program that adds both numbers.
For example:-
Input:
linkedList1: 1 -> 2 -> 3 // represents number 123
linkedList2: 9 -> 8 -> 7 // represents number 987
Output:
resultantLinkedList: 1 -> 1 -> 1 -> 0 // represents number 1110
Explanation:
123 + 987 = 1110
Recommended: Please try to solve Add two numbers represented by a linked list on “CODESTUDIO” first before moving on to the solution.
Now let’s see various approaches to add two numbers represented by a linked list.
Driver code
Let’s check out the main function before moving to each approach. We initialize three linked lists in the main function: first linked list, second linked list, and the resultant linked list.
Main function:
public class Main { public static void main(String[] args) { // linked list 1 ListNode list1 = new ListNode(1); list1.next = new ListNode(2); list1.next.next = new ListNode(3); System.out.print("First Linked List is "); printList(list1); // linked list 2 ListNode list2 = new ListNode(9); list2.next = new ListNode(8); list2.next.next = new ListNode(7); System.out.print("Second Linked List is "); printList(list2); // resultant linked list ListNode result = addTwoNumbers(list1, list2); System.out.print("Resultant Linked List is "); printList(result); } }
Let’s also check out the ListNode class and printList() function, repeatedly used in the program.
Class ListNode:
// class representing the node in the linked class ListNode { int val; ListNode next; ListNode(int val) { this.val = val; } }
Function printList():
// function to print linked list private static void printList(ListNode head) { while (head != null) { System.out.print(head.val + " "); head = head.next; } System.out.println(); }
Add two numbers represented by a linked list: Traversal Approach
In this approach, we reverse the linked lists as the numbers have to be added from the right end. Then traverse through the linked list and add the values one by one from the node. If the sum exceeds 9, the resultant linked list is appended accordingly with the carry and remainder. The result obtained in this approach is reversed, so the linked list must be reversed to get the final result.
Steps:
- Check if any one of the linked lists is empty; return the other linked list.
- Reverse both the linked lists.
- Traverse the linked lists.
- Add the digits each from respective linked lists and traverse to the next node.
- If one of the linked lists has reached the end, then take the remaining digits as 0.
- Continue the above process till the end is reached for both the linked lists.
- If the sum of two digits exceeds 9, the resultant linked list is appended accordingly with the carry and remainder.
- Return the head of the resultant linked list after reversing.
Code:
public class Main { private static ListNode reverseLinkedList(ListNode head) { ListNode previous = null, current = head, next = null; while (current != null) { next = current.next; current.next = previous; previous = current; current = next; } head = previous; return head; } // function to add two numbers private static ListNode addTwoNumbers(ListNode headList1, ListNode headList2) { if (headList1 == null) return headList2; if (headList2 == null) return headList1; ListNode result = null, head = null; int carry = 0; // reverse both the linked lists headList1 = reverseLinkedList(headList1); headList2 = reverseLinkedList(headList2); // while end of list is not reached while (headList1 != null || headList2 != null) { int sum = 0; // add value in linkedlist 1 if (headList1 != null) { sum += headList1.val; headList1 = headList1.next; } // add value in linkedlist 2 if (headList2 != null) { sum += headList2.val; headList2 = headList2.next; } // add carry sum += carry; int value = sum % 10; carry = sum / 10; // node with the remainder value ListNode node = new ListNode(value); if (result != null) { result.next = node; result = result.next; } else { result = head = node; // for the first iteration } } // if carry is present if (carry > 0) { result.next = new ListNode(carry); } head = reverseLinkedList(head); return head; } }
Output:
First Linked List is 1 2 3 Second Linked List is 9 8 7 Resultant Linked List is 1 1 1 0
Complexity Analysis:
- Time Complexity: O(m + n) as the linked lists are traversed once.
- Space Complexity: O(m + n) as extra space is required to store the output numbers.
m: number of nodes in the first linked list
n: number of nodes in the second linked list
Add two numbers represented by a linked list: Using Stack
In this approach, the nodes are passed into stacks. The values are added from the top to the resultant stack. The result obtained in this approach is converted back to a linked list.
Steps:
- Check if any one of the linked lists is empty; return the other linked list.
- Create three stacks: stack1, stack2, stackResult.
- Fill stack1 with node values from the first linked list.
- Fill stack2 with node values from the second linked list.
- Fill stack3 by creating new nodes and setting the new node’s value to the sum of the top values of stack1 and stack3 and carry until list1 and list2 are empty.
- If carry is remaining, then push it into stack3.
- Convert the stack to a linked list and return the linked list.
Code:
import java.util.Stack; public class Main { static ListNode head; static ListNode tail; // function to add node to the linked list private static void appendNode(int value) { // add first node if (head == null) { head = new ListNode(value); tail = head; return; } // add node ListNode node = new ListNode(value); tail.next = node; tail = node; } // function to create a linked list from stack private static ListNode createLinkedList(Stack<Integer> s) { // initialize head as null if the head is pointing to some existing list if (head != null) { head = null; } // add node to linked list till the stack is empty while (!s.isEmpty()) { appendNode(s.pop()); } return head; } // function to add two numbers private static ListNode addTwoNumbers(ListNode headList1, ListNode headList2) { // if first linked list is empty then return the second linked list if (headList1 == null) return headList2; // if first linked list is empty then return the second linked list if (headList2 == null) return headList1; Stack<Integer> stack1 = new Stack<Integer>(); Stack<Integer> stack2 = new Stack<Integer>(); Stack<Integer> stackResult = new Stack<Integer>(); // push headList1 into the first stack ListNode temp = headList1; while (temp != null) { stack1.push(temp.val); temp = temp.next; } // push headList2 into the second stack temp = headList2; while (temp != null) { stack2.push(temp.val); temp = temp.next; } int sum = 0, carry = 0, value1, value2; // add the popped digits till one of the stacks becomes empty while ((!stack1.empty()) && (!stack2.empty())) { value1 = stack1.pop(); value2 = stack2.pop(); sum = (value1 + value2 + carry) % 10; carry = (value1 + value2 + carry) / 10; // store sum in the resultant stack stackResult.push(sum); } // if stack1 still has some digits left, add those digits to the sum while (!stack1.isEmpty()) { value1 = stack1.pop(); sum = (value1 + carry) % 10; carry = (value1 + carry) / 10; stackResult.push(sum); } // if stack2 still has some digits left, add those digits to the sum while (!stack2.isEmpty()) { value2 = stack2.pop(); sum = (value2 + carry) % 10; carry = (value2 + carry) / 10; stackResult.push(sum); } // add remaining carry to the sum if (carry > 0) { stackResult.push(carry); } // return the resultant stack as a linked list return createLinkedList(stackResult); } }
Output:
First Linked List is 1 2 3 Second Linked List is 9 8 7 Resultant Linked List is 1 1 1 0
Complexity Analysis:
- Time Complexity: O(m + n)
- Space Complexity: O(m + n) as extra space is required for stacks.
Add two numbers represented by a linked list: Using Backtracking
In this approach, the concept of recursion and backtracking is used. After the complete traversal of the linked list, the node values are added through backtracking.
Steps:
- Check if any one of the linked lists is empty; return the other linked list.
- Calculate the sizes of both the linked lists.
- Initialize returnedNode to store the previously added value.
- Compare the size of the linked list and pass the linked list with the smaller size first with the respective size to the addition(). The result is stored in returnedNode.
- In addition() if both are of equal size, then a recursive call is made, and both the linked list traverses one node.
- In addition() if both are not of equal size, then a recursive call is made, and the bigger linked list traverses one node.
- Now traverse both linked lists till the end, i.e., till the base condition is reached.
- Through backtracking, addition operations are now performed.
- returnedNode stores the rightmost digit of the latest previous value.
- The node with the current value is returned to obtain the output.
Code:
public class Main { private static ListNode addition(ListNode headList1, ListNode headList2, int size1, int size2) { ListNode node = new ListNode(0); // base case if (headList1.next == null && headList2.next == null) { // add last nodes of both the linked list node.val = (headList1.val + headList2.val); node.next = null; return node; } // a node that contains the sum of previously added number ListNode returnedNode; //i f sizes of both the linked list are the same then move in both linked list if (size2 == size1) { // recursively call the function and move ahead in both linked list returnedNode = addition(headList1.next, headList2.next, size1 - 1, size2 - 1); // add current nodes and append the carry node.val = (headList1.val + headList2.val) + ((returnedNode.val) / 10); } // or else move in big linked list else { // recursively call the function and move ahead in the bigger linked list returnedNode = addition(headList1, headList2.next, size1, size2 - 1); // add the current node value of bigger linked list and append the carry node.val = (headList2.val) + ((returnedNode.val) / 10); } // set returned node with the right most digit returnedNode.val = (returnedNode.val) % 10; // set the returned node to the current node node.next = returnedNode; return node; } // function to add two numbers private static ListNode addTwoNumbers(ListNode headList1, ListNode headList2) { // if first linked list is empty then return the second linked list if (headList1 == null) return headList2; // if first linked list is empty then return the second linked list if (headList2 == null) return headList1; ListNode temp1, temp2, result = new ListNode(0), returnedNode; temp1 = headList1; temp2 = headList2; int size1 = 0, size2 = 0; // find the size of first linked list while (temp1 != null) { temp1 = temp1.next; size1++; } // find the size of second linked list while (temp2 != null) { temp2 = temp2.next; size2++; } // compare the size of linked list and pass the linked list with the smaller size first with the respective size if (size2 > size1) { returnedNode = addition(headList1, headList2, size1, size2); } else { returnedNode = addition(headList2, headList1, size2, size1); } // if the value of returned node is greater than 9 split the digits if (returnedNode.val >= 10) { result.val = (returnedNode.val) / 10; returnedNode.val = returnedNode.val % 10; result.next = returnedNode; } else result = returnedNode; return result; } }
Output:
First Linked List is 1 2 3 Second Linked List is 9 8 7 Resultant Linked List is 1 1 1 0
Complexity Analysis:
- Time Complexity: O(m + n)
- Space Complexity: O(m + n)
Add two numbers represented by a linked list: Recursive approach
In this approach, first, the larger linked list is taken and traversed until both the linked lists have equal sizes. When this condition is hit, the digits and carry are added. After this, the remaining digits in the larger linked list are added to obtain the final result.
Steps:
- Check if any one of the linked lists is empty; return the other linked list.
- Calculate the sizes of both the linked lists.
- If sizes are the same, then calculate the sum using the recursion function add addSameSize.
- If the size is not the same, swap the linked list such that the second list is larger than the first.
- Traverse the number of nodes equal to the difference in sizes in the larger linked list.
- Now when they are of the same size and can be added together.
- After this, add the remaining digits of the bigger linked list along with the carry.
- If carry is left, append a node to the result.
Code:
public class Main { static ListNode headList1, headList2, result, current; static int carry; // function to add node to the linked list private static void appendNode(int val) { ListNode newNode = new ListNode(val); newNode.next = result; result = newNode; } private static void propogatecarry(ListNode list) { // if the difference in the number of nodes are not traversed then add carry if (headList1 != current) { propogatecarry(headList1.next); int sum = carry + headList1.val; carry = sum / 10; sum %= 10; // add sum to result appendNode(sum); } } private static void addSameSize(ListNode list1, ListNode list2) { // check if the list1 is null // if list1 is null then list2 is also null as they are of same size if (list1 == null) return; // recursively add the remaining nodes and get the carry addSameSize(list1.next, list2.next); // add the digits of current nodes and propagated carry int sum = list1.val + list2.val + carry; carry = sum / 10; sum = sum % 10; // add sum to result appendNode(sum); } // function to add two numbers private static ListNode addTwoNumbers(ListNode list1, ListNode list2) { headList1 = list1; headList2 = list2; // if first linked list is empty return second linked list if (headList1 == null) { result = headList2; return result; } // if second linked list is empty return first linked list if (headList2 == null) { result = headList1; return result; } ListNode temp1 = headList1; ListNode temp2 = headList2; int size1 = 0, size2 = 0; // find the size of first linked list while (temp1 != null) { temp1 = temp1.next; size1++; } // find the size of second linked list while (temp2 != null) { temp2 = temp2.next; size2++; } // if linked list of same size if (size1 == size2) { addSameSize(headList1, headList2); } else { // swap linked list if second linked list is larger than first if (size1 < size2) { ListNode temp = headList1; headList1 = headList2; headList2 = temp; } int difference = Math.abs(size1 - size2); // traverse the difference in the first linked list ListNode temp = headList1; while (difference-- >= 0) { current = temp; temp = temp.next; } // add linked list with same size addSameSize(current, headList2); // add the remaining numbers in the first number and carry propogatecarry(headList1); } // add carry to the linked list if (carry > 0) { appendNode(carry); } return result; } }
Output:
First Linked List is 1 2 3 Second Linked List is 9 8 7 Resultant Linked List is 1 1 1 0
Complexity Analysis:
- Time Complexity: O(m + n)
- Space Complexity: O(m + n)
Frequently Asked Questions
A Linked List is a linear data structure where the elements called nodes are stored at non-contiguous memory locations.
The various methods to add two numbers represented by a linked list are backtracking, stacks, normal traversal, etc.
Stacks are linear data structures that allow us to store and retrieve data sequentially. It follows the LIFO, i.e., Last In First Out, for the insertion and abstraction of data.
Recursion is a method of solving a problem that depends on solutions to smaller instances of the same problem. In this, the function calls itself till the base condition is reached.
Key Takeaways
This blog covered the various methods to add two numbers represented by a linked list. The methods discussed are the traversal approach, recursive approach, backtracking approach, and an approach using stacks.
Now that you know how to approach a problem in Linked List try out some questions based on them on our CodeStudio Platform!
Don’t stop here. Check out our Data Structures and Algorithms-guided path to learn Data Structures and Algorithms from scratch. We hope you found this blog useful. Feel free to comment down below if you have a better insight into the above approach.
By: Hari Sapna Nair
Leave a Reply