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 <technic....@gmail.com> 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.