1. Calculate the length of both list (A, B).
2. Find the position in the longer list corresponding to the head of
shorter list, and copy the previous digits to output list C.
(Or for simplicity, appending 0 to the shorter list so as to get the
same length as the longer one)
3. Add the two lists into list C without performing carry.
4. Perform carries. For each digit x in sum C, and the previous digit px.
a) if x < 9, no change to x and px;
b) if x > 9, x = x - 10, px = px + 1;
c) if x ==9, continue to next digit until you come to a digit x'
not equal to 9 (or the end of list)
if x' > 9, x' = x' - 10, px = px + 1, and change all
the 9's in between to 0.
else, keep all those digits untouched.
step 3 and 4 can be merged into one pass.
On 2010-8-25 17:54, Raj N wrote:
Input : Two large singly linked lists representing numbers with most
significant digit as head and least significant as last node.
Output: Difference between the numbers as a third linked list with
Most significant digit as the head.
Eg:
---
Input:
A = 5->4->2->0->0->9->0->0
B = 1->9->9
Output:
C = 5->4->2->0->0->7->0->1
Required complexity :
O(n)
Constraint:
Reversing linked list is NOT allowed
--
You received this message because you are subscribed to the Google Groups "Algorithm
Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
