This is close, but more complicated than necessary. After you know
how many leading zeros are needed before B, just act like they're
present and use recursion to process right-to-left:
#include <stdio.h>
#include <stdlib.h>
typedef struct digit_s {
struct digit_s *next;
int val;
} DIGIT;
DIGIT *new_digit(int val, DIGIT *next)
{
DIGIT *d = malloc(sizeof *d);
d->val = val;
d->next = next;
return d;
}
int length(DIGIT *d)
{
int n = 0;
while (d) {
n++;
d = d->next;
}
return n;
}
void print(DIGIT *d)
{
while (d) {
printf("%d", d->val);
d = d->next;
}
}
static DIGIT *
do_sub(DIGIT *a, int n_leading_zeros, DIGIT *b, int *borrow)
{
DIGIT *rtn;
int b_val, val;
if (a == NULL) { // b is NULL, too
*borrow = 0;
return NULL;
}
if (n_leading_zeros > 0) {
rtn = do_sub(a->next, n_leading_zeros - 1, b, borrow);
b_val = 0;
}
else {
rtn = do_sub(a->next, 0, b->next, borrow);
b_val = b->val;
}
// Subtract including borrow from previous.
val = a->val - b_val - *borrow;
// See if we need to borrow from the next digit.
if (val < 0) {
val += 10;
*borrow = 1;
}
else {
*borrow = 0;
}
return new_digit(val, rtn);
}
DIGIT *subtract(DIGIT *a, DIGIT *b)
{
int borrow;
return do_sub(a, length(a) - length(b), b, &borrow);
}
int main(void)
{
DIGIT *a =
new_digit(5,
new_digit(4,
new_digit(2,
new_digit(0,
new_digit(0,
new_digit(9,
new_digit(0,
new_digit(0, NULL))))))));
DIGIT *b =
new_digit(1,
new_digit(9,
new_digit(9, NULL)));
DIGIT *r = subtract(a, b);
print(a); printf(" - "); print(b);
printf(" = "); print(r); printf("\n");
return 0;
}
On Aug 25, 8:25 am, Terence <[email protected]> wrote:
> 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.
