Wednesday, December 18, 2013

Adding 3 Linked Lists


Last Time we discussed the basics of Linked List Today we will try adding more more than 2 Linked Lists. Although in the program you will see that I have manually created Lists and then adding them in a very constrained manner which can be overcome by introducing dynamic looping as per the program requirements.


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

struct Node
{
    int info;
    struct Node* next;
};

int lenghtOfLinkedList(struct Node*); // This method is count the number of elements in a list and on the basis of max count neutralize all other to bring them to the format of largest one.
void createLinkedListA(struct Node*); // create a sample linked list
void createLinkedListB(struct Node*); // create a sample linked list
void createLinkedListC(struct Node*); // create a sample linked list

Now we have linked lists
A = head->6->7->8->9
B = head->1->2->3
c = head->4->5

void neutralizeLinkedList(struct Node*, int, int); 


Now after neutralizing we have linked lists
A = head->6->7->8->9
B = head->0->1->2->3
C = head->0->0->4->5




void printLinkedList(struct Node*); // To print linked list when required, the print operation will not print the head.

void reverseLinkedList(struct Node*);

Now after neutralizing we want to reverse the linked list so, now we have linked lists

A = head->9->8->7->6
B = head->3->2->1->0
C = head->5->4->0->0


int max(int, int, int); // on the basis of the maximum number of digits we will iterate the loop in this case it is 4

void AddLinkedLists(struct Node*, struct Node*, struct Node*, struct Node*, int);


          A = head->9->8->7->6
          B = head->3->2->1->0
          C = head->5->4->0->0
    ADD = head->7->5->9->6
CARRY=            1    1   0   0

---------------------------------------------PROGRAM-------------------------------------


int main()
{
    struct Node* head1 = (struct Node*)malloc(sizeof(struct Node));
    head1->info = -1;
    head1->next = NULL;
    createLinkedListA(head1);
    printLinkedList(head1);
    
    struct Node* head2 = (struct Node*)malloc(sizeof(struct Node));
    head2->info = -1;
    head2->next = NULL;
    createLinkedListB(head2);
    printLinkedList(head2);
    
    struct Node* head3 = (struct Node*)malloc(sizeof(struct Node));
    head3->info = -1;
    head3->next = NULL;
    createLinkedListC(head3);
    printLinkedList(head3);
    
    struct Node* head4 = (struct Node*)malloc(sizeof(struct Node));
    head4->info = -1;
    head4->next = NULL;
    
    int lenhead1 = lenghtOfLinkedList(head1);
    int lenhead2 = lenghtOfLinkedList(head2);
    int lenhead3 = lenghtOfLinkedList(head3);
    int maxlen = max(lenhead1, lenhead2, lenhead3);
    printf("\n\nMax len is %d",maxlen);
    
    if(lenhead1 < maxlen)
        neutralizeLinkedList(head1, lenhead1, maxlen);
   
    if(lenhead2 < maxlen)
        neutralizeLinkedList(head2, lenhead2, maxlen);
    
    if(lenhead3 < maxlen)
        neutralizeLinkedList(head3, lenhead3, maxlen);
    
    reverseLinkedList(head1);
    reverseLinkedList(head2);
    reverseLinkedList(head3);
    printLinkedList(head1);
    printLinkedList(head2);
    printLinkedList(head3);
        
    AddLinkedLists(head1, head2, head3, head4, maxlen);
    reverseLinkedList(head4);
    printLinkedList(head4);
    return 0;
}

int lenghtOfLinkedList(struct Node* head) 
{
    int n = 0;
    struct Node* temp = NULL;
    temp = head->next;
    
    while(temp)
    {
        n++;
        temp = temp->next;
    }
        
    return n;    
}

void createLinkedListA(struct Node* head1)
{
    struct Node* temp = NULL;
    temp = head1;
    
    struct Node* A = (struct Node*)malloc(sizeof(struct Node));
    A->info = 6;
    A->next = NULL;
    struct Node* B = (struct Node*)malloc(sizeof(struct Node));
    B->info = 7;
    B->next = NULL;
    struct Node* C = (struct Node*)malloc(sizeof(struct Node));
    C->info = 8;
    C->next = NULL;
    struct Node* D = (struct Node*)malloc(sizeof(struct Node));
    D->info = 9;
    D->next = NULL;
    
    temp->next = A;
    A->next = B;
    B->next = C;
    C->next = D;
    //head1->6->7->8->9
}

void createLinkedListB(struct Node* head2)
{
    struct Node* temp = NULL;
    temp = head2;
    
    struct Node* A = (struct Node*)malloc(sizeof(struct Node));
    A->info = 1;
    A->next = NULL;
    struct Node* B = (struct Node*)malloc(sizeof(struct Node));
    B->info = 2;
    B->next = NULL;
    struct Node* C = (struct Node*)malloc(sizeof(struct Node));
    C->info = 3;
    C->next = NULL;
    //struct Node* D = (struct Node*)malloc(sizeof(struct Node));
    //D->info = 9;
    //D->next = NULL;
    
    temp->next = A;
    A->next = B;
    B->next = C;
    //C->next = D;
    //head2->1->2->3
}

void createLinkedListC(struct Node* head3)
{
    struct Node* temp = NULL;
    temp = head3;
    
    struct Node* A = (struct Node*)malloc(sizeof(struct Node));
    A->info = 4;
    A->next = NULL;
    struct Node* B = (struct Node*)malloc(sizeof(struct Node));
    B->info = 5;
    B->next = NULL;
    //struct Node* C = (struct Node*)malloc(sizeof(struct Node));
   // C->info = 3;
    //C->next = NULL;
   // struct Node* D = (struct Node*)malloc(sizeof(struct Node));
   // D->info = 9;
   // D->next = NULL;
    
    temp->next = A;
    A->next = B;
    //B->next = C;
    //C->next = D;
    //head3->4->5;
}

void neutralizeLinkedList(struct Node* head, int currentlen, int reqlen)
{
    int i = 0;
    struct Node* temp = NULL;
    struct Node* newnode = NULL;
    temp = head;
    
    while(i < (reqlen - currentlen))
    {
        newnode = (struct Node*)malloc(sizeof(struct Node));
        newnode->info = 0;
        newnode->next = NULL;
        
        newnode->next = temp->next;
        temp->next = newnode;
        i++;
    }
}

void printLinkedList(struct Node* head)
{
    printf("\n\n Print Linked List\n\n");
    struct Node* temp = NULL;
    temp = head->next;
    
    while(temp)
    {
        printf("%d",temp->info);
        temp = temp->next;
    }
}

void reverseLinkedList(struct Node* head)
{
    int i = 0;
    struct Node* temphead = NULL;
    struct Node* first = NULL;
    struct Node* last = NULL;
    struct Node* slast = NULL;
    struct Node* tempend = NULL;
    
    temphead = head;
    first = head->next;
    last = head->next;
    slast = head;
    tempend = head;
    
    while(first->next != NULL)
    {
        while(last->next != NULL)
        {
            last = last->next;
            slast = slast->next;
        }
        
        tempend = last;
        
        if(i == 0)
        {
            temphead->next = tempend;
            i++;
        }
        
        tempend->next = slast;
        slast->next = NULL;
        slast = first;
        last = slast->next;
    }
}

void AddLinkedLists(struct Node* head1, struct Node* head2, struct Node* head3, struct Node* head4, int maxlen)
{
    int add = 0;
    int num = 0;
    int carry = 0;
    int i = 0;
    
    struct Node* temphead1 = head1->next;
    struct Node* temphead2 = head2->next;
    struct Node* temphead3 = head3->next;
    struct Node* temphead4 = head4;
    struct Node* newnode = NULL;
    
    while(i < maxlen)
    {
        add = temphead1->info + temphead2->info + temphead3->info;
        num = add%10 + carry;
        newnode = (struct Node*)malloc(sizeof(struct Node));
        newnode->info = num;
        newnode->next = NULL;
          
        temphead4->next = newnode;
        
        temphead1 = temphead1->next;
        temphead2 = temphead2->next;
        temphead3 = temphead3->next;
        temphead4 = temphead4->next;
        
        carry = add/10;          
        i++;
    }
    
    if(carry != 0)
    {
        newnode = (struct Node*)malloc(sizeof(struct Node));
        newnode->info = carry;
        newnode->next = NULL;
        
        temphead4->next = newnode;
    }
}

int max(int i, int j ,int k)
{
    if(i >= j)
    {
        if(i >= k)
            return i;
        else
            return k;
    }
    else if(j > i)
    {
        if(j >= k)
            return j;
        else
            return k;
    }
}

No comments:

Post a Comment