Let’s discuss a very interesting problem add two numbers represented by linked lists.
Problem Statement –
Given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and least significant digit comes last. Each of the linked list node contain a single digit.
We have to write a code to add the two numbers and return it as a linked list.
Both the numbers do not contain any leading zero, except the number 0 itself.
NOTE: Reversing a linked list is not allowed.
For Example –
List 1 : 7 -> 2 -> 4 -> 3 -> NULL
List 2 : 5 -> 6 -> 4 -> NULL
Result : 7 -> 8 -> 0 -> 7 -> NULL
Explanation : The first linked list is representing the number 7243 and the second linked is representing the number 564. If we add these two numbers we get 7807, which we have to return in the form of a linked list.
We have discussed the problem statement. In this problem, reversing a list is not allowed. How do we add the numbers represented by two linked lists? Do we need any additional data structure for solving this problem.
Programming questions on linked list
Add Two Numbers Represented By Linked Lists – Java Code
To solve this problem, Here i am using additional data structure stack.
The addition of numbers will start from the least significant digit and it is present at the end of the list. The idea here is two use two stacks, first we traverse both the lists and put the node values in a stack.
Then we run a loop until any of the stack is not empty and we do the addition and create a result linked list.
Check if a linked list is palindrome or not
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
//Add Two Numbers II - Java Code class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { Stack<Integer> stack1 = addListValToStack(l1); Stack<Integer> stack2 = addListValToStack(l2); ListNode head = null; int carry = 0; while(stack1.size() > 0 || stack2.size() > 0 || carry != 0) { int sum = carry; if(stack1.size() > 0) sum += stack1.pop(); if(stack2.size() > 0) sum += stack2.pop(); ListNode newNode = new ListNode(sum % 10); newNode.next = head; head = newNode; carry = sum / 10; } return head; } private Stack<Integer> addListValToStack(ListNode list) { Stack<Integer> st = new Stack<>(); while(list != null) { st.add(list.val); list = list.next; } return st; } } |
