add 2 linklist

3->1->5  +    5->9->2 ,

you get

8->0->8

 

3->1->5 + 5->9->4

you get

8->0->0->1

#include<stdlib.h>
#include<stdio.h>

typedef struct node
{
    int data;
    struct node *next;
}*Linklist;

Linklist initLinklist( );

Linklist insert( Linklist l, int num );

Linklist add( Linklist l1, Linklist l2 );

int main( void )
{
    Linklist list1, list2, result;
    list1 = initLinklist(  );
    list2 = initLinklist(  );

    list1 = insert( list1, 5 );
    list1 = insert( list1, 1 );
    list1 = insert( list1, 3 );
    list2 = insert( list2, 4 );
    list2 = insert( list2, 9 );
    list2 = insert( list2, 5 );
    //list1 = insert( list1, 3 );

    result = add( list1, list2 );
    while( result != NULL )
    {
        printf( "%d--> ", result->data );
        result = result->next;
    }

    return 0;
}

Linklist initLinklist(  )
{
    Linklist l = ( Linklist ) malloc( sizeof( Linklist ) );
    if( l == NULL )
    {
        printf("allocate memory failed...");
        exit( 1 );
    }
    else
    {
        l->data = 0;
        l->next = NULL;
    }
    return l;
}

Linklist insert( Linklist l, int num )
{
    Linklist temp = ( Linklist )malloc( sizeof( Linklist ) );
    if( temp == NULL )
    {
        printf("allocate memory failed...");
        exit( 1 );
    }
    else
    {
        temp->data = num;
        temp->next = l->next;
    }
    l->next = temp;

    return l;
}

Linklist add( Linklist l1, Linklist l2 )
{
    if( l1 == NULL && l2 == NULL )
    {
        return NULL;
    }
    Linklist p1 = l1;
    Linklist p2 = l2;
    Linklist result;
    result = initLinklist( );
    int carryFlag = 0;
    p1 = p1->next;
    p2 = p2->next;
    while( p1 != NULL && p2 != NULL )
    {
        int tempData = p1->data + p2->data + carryFlag;
        // rest the flag be 0 after sum
        carryFlag = 0;
        if( tempData >= 10 )
        {
            tempData = tempData - 10;
            carryFlag = 1;
        }
        result = insert( result, tempData );
        p1 = p1->next;
        p2 = p2->next;
    }
    // critical, if carryflag = 1, need to add a additional node
    // for ex, 3->1->5 + 5->9->4
    // you should get 8->0->0---->1, dont' forget the 1.
    if( carryFlag == 1 )
    {
        result = insert( result, 1 );
    }
    while( p1 != NULL )
    {
        result = insert( result, p1->data );
        p1 = p1->next;
    }
    while( p2 != NULL )
    {
        result = insert( result, p2->data );
        p2 = p2->next;
    }
    return result;
}

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s