Be the first user to complete this post

  • 0
 Add to List
Medium

34. Add two numbers represented by a linked list, Numbers are Stored in REVERSE 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:

  1. Initialize carry =0 and newHead for Result linked list
  2. Iterate both the linked lists at the same time.
    • Get the sum S = node value from both the lists + carry (if any of the list is over, take 0 as node value from that list)
    • Reset carry=0
    • If S > 10, then do S = S-10, carry=1.
    • Create a new node with value S and add it to the newHead.
  3. Repeat the above step until both the lists are over. 
  4. At the end, check if carry =1, create a node with value 1 and add to result list.
  5. Return result list.
  6. Look at the display functions below for printing linked lists in forward and reverse order.

Example:

First Number: 179    Second Number: 86

Add two numbers represented by a linked list, Number Stored in REVERSE order
First Number in REVERSE order: 5957
Second Number in REVERSE order : 59
Addition in REVERSE order : 0967
Actual Result in FORWARD ORDER : 9670

Also Read - Adding Two Numbers with Linked Lists

Related Problems: