**We have similar post – Two numbers represented by a linked list, Number Stored in FORWARD order
**

**Objective:** Two numbers represented by a linked list where each node contains single digit. The digits are stored in REVERSE order, means head is pointing to the first digit of the number.

**Input:** Two numbers represented by Linked Lists

**Output: **Addition of two numbers represented by a Linked List.

**Example: **

First Number in REVERSE order: 5957 Second Number in REVERSE order : 59 Addition in REVERSE order : 0967 Actual Result in FORWARD ORDER : 9670

**Approach:**

- Take a variable int
**carry**=0. - Initialize Node
**newHead**= null; and Node**curr**= null. - newHead will be the starting node of our result linked list and curr node will the reference to the current node on which we are working in our result linked list.
- Navigate Both the lists simultaneously taking one node at a time.
- Add the data of nodes and carry , say you call this as total.
- Check if total >=10, if yes put carry =1 and total=total-10.
- create a new node with value total, say you call it as Node ‘n’.
- check if newHead is null, if yes then and assign ‘n’ to newHead. Now our starting node of result linked list is fixed.
- if newHead is not null then add ‘n’ to the result linked list with the help of newHead and curr.
- Now repeat steps 4 to 9 till any one of the list gets over( considering both the list has different length, if both list has the same length then both lists gets over at the same time, you will not need step 11).
- Now navigate the list ( whichever is remaining) and add it to the result list. (take care of the carry, see Example).
*You can avoid this step by making sure that both the list has the same length adding 0 at the end of the shorter list , to see the similar implementation click here.* - At the End check the carry, if it is not 0, create a new node with value 1 and add it to the result linked list.

**Example: **

First Number : 179Second Number : 86

(Click on the image to enlarge it)

**Complete Code:**

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

public class LinkedListAddtionReverseOrder { | |

public Node add(Node h1, Node h2){ | |

int carry = 0; | |

Node newHead = null; | |

Node curr=null; | |

while(h1!=null && h2!=null){ | |

int a = h1.data; | |

int b = h2.data; | |

int total = a+b+carry; | |

if(total>=10){ | |

carry = 1; | |

total = total–10; | |

} | |

if(newHead==null){ | |

newHead = new Node(total); | |

curr = newHead; | |

}else{ | |

Node n = new Node(total); | |

curr.next = n; | |

curr = curr.next; | |

} | |

h1=h1.next; | |

h2=h2.next; | |

} | |

while(h1!=null){ | |

int x= h1.data + carry; | |

Node n = new Node(x); | |

curr.next = n; | |

curr = curr.next; | |

h1=h1.next; | |

carry=0; | |

} | |

while(h2!=null){ | |

int x= h2.data + carry; | |

Node n = new Node(x); | |

curr.next = n; | |

curr = curr.next; | |

h2=h2.next; | |

carry=0; | |

} | |

if(carry>0){ | |

Node n = new Node(1); | |

curr.next = n; | |

curr = curr.next; | |

} | |

return newHead; | |

} | |

public void display(Node head){ | |

Node currNode = head; | |

while(currNode!=null){ | |

System.out.print("" + currNode.data); | |

currNode=currNode.next; | |

} | |

} | |

public void displayReverse(Node head){ | |

Node currNode = head; | |

if(head==null){ | |

return; | |

} | |

display(head.next); | |

System.out.print(head.data); | |

} | |

public static void main(String args[]){ | |

LinkedListAddtionReverseOrder l = new LinkedListAddtionReverseOrder(); | |

Node h1 = new Node(5); | |

h1.next= new Node(9); | |

h1.next.next = new Node(5); | |

h1.next.next.next = new Node(7); | |

System.out.print("First Number in REVERSE order: "); | |

l.display(h1); | |

Node h2 = new Node(5); | |

h2.next= new Node(9); | |

System.out.print("\n Second Number in REVERSE order : "); | |

l.display(h2); | |

Node x = l.add(h2, h1); | |

System.out.print("\n Addition in REVERSE order : "); | |

l.display(x); | |

System.out.print("\n Actual Result in FORWARD ORDER : "); | |

l.displayReverse(x); | |

} | |

} | |

class Node{ | |

public int data; | |

public Node next; | |

public Node(int data){ | |

this.data = data; | |

this.next = null; | |

} | |

} |

**Output**:

First Number in REVERSE order: 5957 Second Number in REVERSE order : 59 Addition in REVERSE order : 0967 Actual Result in FORWARD ORDER : 9670

Found two bugs in the above code.

1) in first while loop if carry becomes 1 no where carry is set to ‘0’ again. once carry value is ‘1’ it will always be ‘1’.

should be like this..

if (total >= 10) {

carry = total / 10;

total %= 10;

} else

carry = 0;

2) If the input given as “1” && “99” above program results 010..it should be 001

in while (l1!=null) && while(l2!=null) loop creating new node with the total. If the total is 10 then it will create node with 10. Inside need to have condition as below.

if (total >= 10) {

carry = total / 10;

total %= 10;

} else

carry = 0;