We can take the two's complement of the smaller number and add it to the
first.
a) Get Number from 1st linked List. - num1
b) Get Number from 2nd Linked List - num2
c) Get Two's complement of smaller number and add it to the larger number.
d) Create a linked list of the result.
On Thu, Aug 26, 2010 at 8:28 AM, Gene <gene.ress...@gmail.com> wrote:
> 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<algogeeks%2bunsubscr...@googlegroups.com>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
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.
