a c program to add two singly linked lists, of unequal lengths containing single digited numbers in all of their nodes

Question

i got this as an interview question. i was given 2 linked lists of unequal lengths,containing a single digited number in each of their nodes. i was asked to build a 3rd linked list which contains the sum of the two linked lists, again in the form of 1 digit in a node. ex: linked list 1 is 4-7-9-6 linked list 2 is 5-7 then the 3rd linked list would be 4-8-5-3 can someone suggest me an efficient algorithm, with minimum compromise in terms of space complexity?(i am not expecting an algo dat involves reversing the lists many times).

Answer 1

1. Reverse lists 1 and 2
2. Sum element-by-element (while maintaining a carry), putting the results in a list 3 that you construct from tail to head

OR

1. Convert lists 1 and 2 to ints (e.g. int list1AsInt = 0; For each node {list1AsInt *= 10; list1AsInt += valueOfThisNode;} )
2. Sum those ints
3. Convert the result to a linked list (e.g. valueOfBrandNewNode = list3AsInt % 10; list3AsInt /= 10; Add a new node that points to the prev one; )

OR

1. Traverse both lists once to find out their lengths. For this example, let's assume that list 1 is longer by N nodes.
2. Create a list 3 to represent the sum without carries and a list 4 to represent the carries.
3. For the first N nodes of list 1, copy those values to list 3 and make list 4's values be 0.
4. For the remaining nodes of lists 1 and 2, sum element-by-element, putting the sum mod 10 in list 3 and the carry in list 4. Keep track via a bool of whether list 4 is all 0's.
5. Add a last node with value 0 to list 4.
6. If list 4 is entirely 0's, done. Else, recurse to step 2, treating list 3 as the new list 1 and list 4 as the new list 2. We know the length of the new list 1 is the larger of the lengths of the old lists 1 and 2, and the length of the new list 2 is one more than that.

Answer 2

1. Read each digit as its ASCII equivalent into a char array indexed from 0, for both lists.
2. Use the atoi() function on both char arrays ( you may use atol() or atoll() if you are concerned about the length)
3. Add both numbers
4. Use the itoa() function to convert to a char array & then put back into new list.

Although, I admit the itoa() function is not standard.

Answer 3

If the lists are doubly linked it's easy:

1. Traverse both lists to the end.
2. Add the digits in corresponding nodes, and keep the carry digit.
3. Create the node in list 3.
4. Move one node towards the start of the lists and repeat.

Answer 4

The solution could be much simpler if the list stored the numbers in reverse order.

Nevertheless, with the given constraint, here is an approach.

1. find the nthToLast digit of both lists, starting with n = 0,
2. create a node with the sum of the digits,
3. update the (running) carry,
4. insert the newly created node at the head of the result list

Following is the (untested) C code.

typedef struct DigitNode_ {
    int digit;
    struct DigitNode_ * next;
} DigitNode;

/*  Returns the n-th element from the end of the SLL;
    if no such element exists, then return NULL.
    See: http://stackoverflow.com/questions/2598348/
*/
extern DigitNode * nthNodeFromTail( DigitNode * listHead, size_t n );

/*  Push pNode in the front, i.e. as the new head of the list */
extern void pushFront( DigitNode ** pListHead, DigitNode * pNode );

/*  Create new list as sum of a and b, and return the head of the new list.
        a -> 4 -> 7 -> 9 -> 6 -> NULL
        b ->           5 -> 7 -> NULL
    results in
        c -> 4 -> 8 -> 5 -> 3 -> NULL
*/
DigitNode * sumDigitLists( DigitNode * a, DigitNode * b ) {

    DigitNode * c = 0;
    int carry = 0;

    /* i is the position of a node from the tail of the list, backwards */
    for( size_t i = 0; /* see 'break' inside */; i++ ) {

        const DigitNode * const ithNodeA = nthNodeFromTail( a, i );
        const DigitNode * const ithNodeB = nthNodeFromTail( b, i );

        /* Stop when processing of both lists are finished */
        if( !ithNodeA && !ithNodeB ) {
            break;
        }

        const int ithDigitA = ithNodeA ? ithNodeA->digit : 0;
        const int ithDigitB = ithNodeB ? ithNodeB->digit : 0;

        assert( (0 <= ithDigitA) && (ithDigitA <= 9) );
        assert( (0 <= ithDigitB) && (ithDigitB <= 9) );

        const int conceptualIthDigitC = carry + ithDigitA + ithDigitB;
        const int ithDigitC = conceptualIthDigitC % 10;
        carry = conceptualIthDigitC / 10;

        DigitNode ithNodeC = { ithDigitC, NULL };
        pushFront( &c, &ithNodeC ); 
    }

    return c;
}