Wednesday 8 June 2016

Find the middle node in the linked list

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

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

void AppendToList (struct node **head, int value)
{
        struct node *newNode = NULL;

        newNode = (struct node *) malloc(sizeof(struct node));
        if (newNode == NULL)
                return;

        newNode->data = value;
        newNode->next = NULL;

        if (*head == NULL)
                        *head = newNode;
        else {
                newNode->next = *head;
                *head   = newNode;
        }

        return;
}

void PrintList (struct node **head)
{
        struct node *temp = *head;

        while (temp) {
                printf("%d\r\n", temp->data);
                temp = temp->next;
        }

        return;
}

/* traverse double the time
 * return the first pointer
 * basically divide by 2 algorithm
 * **/
void FindMiddleNode (struct node **head, struct node **middle)
{
        struct node *temp1, *temp2;

        temp1 = temp2 = *head;

        while (temp2 != NULL) {
                temp1 = temp1->next;
                temp2 = temp2->next->next;
        }
        *middle = temp1;

        return;
}

int main(void)
{
        int i;
        struct node *head = NULL;
        struct node *middle = NULL;

        for (i = 1; i <= 10; i++) {
                AppendToList(&head, i);
        }

        printf("List \r\n");
        PrintList(&head);

        FindMiddleNode(&head, &middle);
        printf("Middle Node %d \r\n", middle->data);

        return 0;
}



Makefile: 


CC = gcc

CFLAGS = -g -Wall

all: mergenode findAndRemoveLoop middlenode

mergenode: mergenode.o
        ${CC} ${CFLAGS} -o $@ mergenode.o

findAndRemoveLoop: findAndRemoveLoop.o
        ${CC} ${CFLAGS} -o $@ findAndRemoveLoop.o

middlenode: middlenode.o
        ${CC} ${CFLAGS} -o $@ middlenode.o

clean:
        -@rm *.o

distclean: clean
        -@rm    mergenode
        -@rm    findAndRemoveLoop
        -@rm    middlenode


Output: 

List
10
9
8
7
6
5
4
3
2
1
Middle Node 5

No comments:

Post a Comment