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 FORWARD order

This post is the exten­sion of   — Two num­bers rep­re­sented by a linked list, Num­ber Stored in REVERSE 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 For­ward order, means head is point­ing to the last 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 : 1007
Second Number : 93
Addition : 1100

 

Two numbers represented by a linked list, Number Stored in FORWARD order

Two num­bers rep­re­sented by a linked list, Num­ber Stored in FORWARD order

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.
  • Append 0 in front Shorter List

    Append 0 in front Shorter List

  • Cre­ate a global vari­able carry=0.
  • Cre­ate a new­Head = null;
  • 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.
  • Now using recur­sion travel in both the list till the end.
  • So now nodes are stores in a stack
  • Now while com­ing 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 cre­ate a new node with sum-10
  • Else just cre­ate a new Node with sum.
  • Add the newly cre­ated node to the result linked list with the help of newHead.

Com­plete Code:


Out­put:

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

You may also like...

  • indra senarao

    Above solu­tion gives wrong out­put for the inputs like below :

    First Num­ber : ->1->1->1->7
    Sec­ond Num­ber : ->9->9->9->9
    Addi­tion : ->1->1->1->6

    There is no extra last carry bit added accord­ing to the exist­ing code. Please mod­ify the logic accordinglty

    • tuto­ri­al­hori­zon

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

  • Sid­dhi Mohite

    Can I get the code/algorithm for adding two binary num­bers using dou­bly linked lists in cpp?

  • biswa­jit singh

    hey i think this can be done in a rel­a­tively eas­ier man­ner using iter­a­tive method. we could main­tain 2 queues and store ele­ments of these linked lists in the queues. we could then pop these ele­ments out and keep adding them to 2 dif­fer­ent strings . after that we could con­vert these strings into inte­ger and out­put the num­ber in the form of a linked list. takes up extra space tho!