Let’s discuss a problem add two numbers as lists and their java code.
Given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. We have to write a code to add these two numbers and return the sum as a linked list.
For this problem, you may assume the two numbers do not contain any leading zero, except the number 0 itself.
For example –
Linked List 1 : 2 -> 4 -> 6 -> NULL
Linked List 2 : 5 -> 6 -> 4 -> NULL
Result : 7 -> 0 -> 1 -> 1 -> NULL
Explanation :
In this example first, we added 2 and 5 the result is 7. Then, 6 and 4 the result is 10, so we put 0 and take 1 as a carry. Then, we added 6, 4, and 1 (carry) the result is 11, so we put 1 and take 1 as a carry.
Now, the question is how we can approach this problem.
Programming questions on linked list
Add Two Numbers Represented by Linked Lists – Java Code
The easiest approach is to traverse both the linked lists and add the numbers. If the sum is greater than 9 then we have to take the carry and handle this case.
|
1 2 3 4 5 6 7 |
//Structure of node public class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } |
|
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 37 38 |
//Add two numbers public ListNode addTwoNumbers(ListNode l1, ListNode l2) { //Declare a list to store it's result and head pointer ListNode head = new ListNode(0); ListNode result = head; //Two variables one for carry and other for sum int carry = 0; int sum = 0; //Run a loop while condition is true while(l1 != null || l2 != null || carry != 0) { //For each iteration set the value of sum to zero sum = 0; //If linked list 1 is not empty if(l1 != null) { sum = sum + l1.val; l1 = l1.next; } //If linked list 2 is not empty if(l2 != null) { sum = sum + l2.val; l2 = l2.next; } sum = sum + carry; carry = sum/10; //Create a new node result.next = new ListNode(sum%10); result = result.next; } return head.next; } |
Add Two Numbers as Lists InterviewBit Solution
We have already discussed the logic, let’s write a code to solve this problem.
Add two numbers video tutorial
|
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 |
//Add Two Numbers as Lists - Java Code public ListNode addTwoNumbers(ListNode A, ListNode B) { ListNode result = new ListNode(-1); ListNode temp = result; int carry = 0; int sum = 0; while(A != null || B != null || carry != 0) { sum = 0; if(A != null) { sum = sum + A.val; A = A.next; } if(B != null) { sum = sum + B.val; B = B.next; } sum = sum + carry; temp.next = new ListNode(sum%10); temp = temp.next; carry = sum /10; } return result.next; } |
