**This post is the extension of – Two numbers represented by a linked list, Number Stored in REVERSE order
**

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

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

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

**Example: **

First Number : 1007 Second Number : 93 Addition : 1100

** **

**Approach:**

- Get the length of both the lists.
- If lengths are not equal, make them equal by adding nodes with value 0 in front of shorter linked list.
- Create a global variable carry=0.
- Create a newHead = 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.
- Now using recursion travel in both the list till the end.
- So now nodes are stores in a stack
- Now while coming back, each node will pop out from the stack in reverse order
- Take node data from both the lists add them along with carry.
- if sum is >=10 , then make carry as 1 and create a new node with sum-10
- Else just create a new Node with sum.
- Add the newly created node to the result linked list with the help of newHead.

**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 AddLinkedListForwardOrder { | |

public int carry=0; | |

public Node newHead = null; | |

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

//first we will make sure that both the Linked list has same no of nodes | |

// to ensure that we will append 0 in front of shorter list | |

int h1Len = getLength(h1); | |

int h2Len = getLength(h2); | |

if(h1Len>h2Len){ | |

int diff = h1Len–h2Len; | |

while(diff>0){ | |

Node n = new Node(0); | |

n.next = h2; | |

h2=n; | |

diff—; | |

} | |

} | |

if(h1Len<h2Len){ | |

int diff = h2Len–h1Len; | |

while(diff>0){ | |

Node n = new Node(0); | |

n.next = h1; | |

h1=n; | |

diff—; | |

} | |

} | |

Node newHead = addBackRecursion(h1, h2); | |

//check for the carry forward, if not 0 then we need to create another node for the end | |

//example adding 1->1 and 9->9 then recursive function will return 0->0 and carry =1 | |

if(carry!=0){ | |

Node n = new Node(carry); | |

n.next = newHead; | |

newHead = n; | |

} | |

return newHead; | |

} | |

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

if(h1==null && h2==null){ | |

return null; | |

} | |

addBackRecursion(h1.next, h2.next); | |

int a = h1.data + h2.data + carry; | |

carry=0; | |

//System.out.println(a); | |

if(a>=10){ | |

carry =1; | |

a = a%10; | |

} | |

Node n = new Node(a); | |

if(newHead==null){ | |

newHead =n; | |

}else{ | |

n.next = newHead; | |

newHead = n; | |

} | |

//carry=0; | |

return newHead; | |

} | |

public int getLength(Node head){ | |

int len=0; | |

while(head!=null){ | |

len++; | |

head = head.next; | |

} | |

return len; | |

} | |

public void display(Node head){ | |

Node currNode = head; | |

while(currNode!=null){ | |

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

currNode=currNode.next; | |

} | |

} | |

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

AddLinkedListForwardOrder l = new AddLinkedListForwardOrder(); | |

Node h1 = new Node(1); | |

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

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

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

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

l.display(h1); | |

Node h2 = new Node(9); | |

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

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

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

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

l.display(h2); | |

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

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

l.display(x); | |

} | |

} | |

class Node{ | |

public int data; | |

public Node next; | |

public Node(int data){ | |

this.data = data; | |

this.next = null; | |

} | |

} |

**Output**:

First Number : ->1->0->0->7 Second Number : ->9->3 Addition : ->1->1->0->0

Above solution gives wrong output for the inputs like below :

First Number : ->1->1->1->7

Second Number : ->9->9->9->9

Addition : ->1->1->1->6

There is no extra last carry bit added according to the existing code. Please modify the logic accordinglty

Thanks a lot indra, i have corrected the code. Let me know if you see errors in this or other posts

Can I get the code/algorithm for adding two binary numbers using doubly linked lists in cpp?

hey i think this can be done in a relatively easier manner using iterative method. we could maintain 2 queues and store elements of these linked lists in the queues. we could then pop these elements out and keep adding them to 2 different strings . after that we could convert these strings into integer and output the number in the form of a linked list. takes up extra space tho!