Table of Contents
If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.
Java Linked List Interview Programs:
- How to reverse a linked list in java
- How to reverse a linked list in pairs in java
- How to find middle element of linked list in java
- How to detect a loop in linked list in java
- Find start node of loop in linkedlist
- How to find nth element from end of linked list
- How to check if linked list is palindrome in java
- Add two numbers represented by linked list in java
Given two number represent by linked list, calculate sum of the numbers and store result in new linked list. Each node of linked list is represented by single digit and head node is most significant digit.
For example:
Sum of two number:
56712
+ 6359
———–
63071
So it will be represented in below format as linked list:
Algorithm:
- Create two linkedlist which will represent above two numbers.
- Reverse both linked list.
- Add two node values (Each node is being represented as single digit) starting from heads of two linkedlist.
- If sum is of above two node values is more than 10, then forward the carry.
- Follow basic mathematical rules for addition.
Below image will make it clear:
- Reverse the result , so that we will get actual sum of numbers.
Java program:
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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 |
package org.arpit.java2blog; public class AddTwoNumberLinkedList{ /* * @Author: Arpit Mandliya * */ private static Node head; private static class Node { private int value; private Node next; Node(int value) { this.value = value; } } public void addToTheLast(Node node) { if (head == null) { head = node; } else { Node temp = head; while (temp.next != null) temp = temp.next; temp.next = node; } } public void printList(Node printNode) { Node temp = printNode; while (temp != null) { System.out.format("%d ", temp.value); temp = temp.next; } System.out.println(); } public static Node reverseLinkedList(Node node) { if (node == null || node.next == null) { return node; } Node remaining = reverseLinkedList(node.next); node.next.next = node; node.next = null; return remaining; } // This function will do sum of numbers represented by linked list public Node findSumOfNumbers(Node l1, Node l2) { int carry =0; Node newHead = null; Node tempNodeForIteration=null; int sum=0; int firstIter=0; while(l1!=null || l2!=null) { firstIter++; sum=carry; if(l1!=null) { sum=sum+l1.value; l1=l1.next; } if(l2!=null) { sum=sum+l2.value; l2=l2.next; } carry=sum/10; sum=sum%10; // Check if it first node for the result if(firstIter==1) { tempNodeForIteration = new Node(sum); newHead=tempNodeForIteration; } else { Node tempSumNode=new Node(sum); tempNodeForIteration.next=tempSumNode; tempNodeForIteration=tempNodeForIteration.next; } } if(carry!=0) { Node tempNode=new Node(carry); tempNodeForIteration.next=tempNode; } return newHead; } public static void main(String[] args) { AddTwoNumberLinkedList list = new AddTwoNumberLinkedList(); // Creating a linked list Node head1=new Node(5); list.addToTheLast(head1); list.addToTheLast(new Node(6)); list.addToTheLast(new Node(7)); list.addToTheLast(new Node(1)); list.addToTheLast(new Node(2)); System.out.print("Number 1: "); list.printList(head1); head=null; Node head2=new Node(6); list.addToTheLast(head2); list.addToTheLast(new Node(3)); list.addToTheLast(new Node(5)); list.addToTheLast(new Node(9)); System.out.print("Number 2: "); list.printList(head2); // Reversing first linkedList head1=reverseLinkedList(head1); //Reversing second linkedList head2=reverseLinkedList(head2); // function to find sum of two linkedlist represent by number Node result= list.findSumOfNumbers(head1,head2); // Reverse the above linkedlist to get actual sum result=reverseLinkedList(result); System.out.print("Sum: "); list.printList(result); } } |
1 2 3 4 5 |
Number 1: 5 6 7 1 2 Number 2: 6 3 5 9 Sum: 6 3 0 7 1 |
.
Was this post helpful?
Let us know if this post was helpful. Feedbacks are monitored on daily basis. Please do provide feedback as that\'s the only way to improve.