Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Add two numbers represented by a linked list, Numbers are Stored in REVERSE order

We have sim­i­lar post — Two num­bers rep­re­sented by a linked list, Num­ber Stored in FORWARD order

Objec­tive: Two num­bers rep­re­sented by a linked list where each node con­tains sin­gle digit. The dig­its are stored in REVERSE order, means head is point­ing to the first digit of the number.

Input: Two num­bers rep­re­sented by Linked Lists

Out­put: Addi­tion of two num­bers rep­re­sented by a Linked List.

Exam­ple:

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

Approach:

  1. Take a vari­able int carry =0.
  2. Ini­tial­ize Node new­Head = null; and Node curr = null.
  3. new­Head will be the start­ing node of our result linked list and curr node will the ref­er­ence to the cur­rent node on which we are work­ing in our result linked list.
  4. Nav­i­gate Both the lists simul­ta­ne­ously tak­ing one node at a time.
  5. Add the data of nodes and carry , say you call this as total.
  6. Check if total >=10, if yes put carry =1 and total=total-10.
  7. cre­ate a new node with value total, say you call it as Node ‘n’.
  8. check if new­Head is null, if yes then and assign ‘n’ to new­Head. Now our start­ing node of result linked list is fixed.
  9. if new­Head is not null then add ‘n’ to the result linked list with the help of new­Head and curr.
  10. Now repeat steps 4 to 9 till any one of the list gets over( con­sid­er­ing both the list has dif­fer­ent length, if both list has the same length then both lists gets over at the same time, you will not need step 11).
  11. Now nav­i­gate the list ( whichever is remain­ing) and add it to the result list. (take care of the carry, see Exam­ple). You can avoid this step by mak­ing sure that both the list has the same length adding 0 at the end of the shorter list , to see the sim­i­lar imple­men­ta­tion click here.
  12. At the End check the carry, if it is not 0, cre­ate a new node with value 1 and add it to the result linked list.

Exam­ple:

First Number : 179
Second Number : 86
Add two numbers represented by a linked list, Number Stored in REVERSE order

Add two num­bers rep­re­sented by a linked list, Num­ber Stored in REVERSE order

Com­plete Code:


Out­put:

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

You may also like...