Knowledge Share: June 2016

Tuesday 14 June 2016

Reverse 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;
}

void ReverseList (struct node **head)
{
        struct node *prev = NULL, *curr = *head, *next = NULL;

        while (curr != NULL) {
                        next = curr->next;
                        curr->next = prev;
                        prev = curr;
                        curr = next;
        }
        *head = prev;

        return;
}

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

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

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

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

        return 0;
}

CC = gcc

CFLAGS = -g -Wall

all: reverselist

reverselist: reverselist.o
        ${CC} ${CLAGS} -o $@ reverselist.o

clean:
        -@rm *.o

Swap linked list node without swapping data

swapnode.c
#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;
}

void swapNodes (struct node **head, int a, int b)
{
        struct node *prev_x, *curr_x;
        struct node *prev_y, *curr_y, *temp;

        curr_x = *head;
        while (curr_x && (curr_x->data != a)) {
                prev_x = curr_x;
                curr_x = curr_x->next;
        }

        curr_y = *head;
        while (curr_y && (curr_y->data != b)) {
                prev_y = curr_y;
                curr_y = curr_y->next;
        }

        prev_x->next = curr_y;
        temp                             = curr_y->next;
        curr_y->next = curr_x->next;

        prev_y->next = curr_x;
        curr_x->next = temp;

        return;
}

int main(int argc, char *argv[])
{
        int i;
        struct node *head = NULL;

        if (argc <= 2) {
                printf("usage: ./swapnode <a> <b> \r\n");
                return 0;
        }

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

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

        swapNodes(&head, atoi(argv[1]), atoi(argv[2]));
        printf("After swap\r\n");
        PrintList(&head);

        return 0;
}

CC = gcc

CFLAGS = -g -Wall

all : swapnode
swapnode: swapnode.o
        ${CC} ${CFLAGS} -o $@ swapnode.o

clean:
        -@rm *.o

Wednesday 8 June 2016

Linked List FIFO

FIFO List

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

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

void InsertToFIFO (struct node **head, struct node **tail, 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;
                        *tail = newNode;
        } else {
                        (*tail)->next = newNode;
                        *tail   = newNode;
        }

        return;
}

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

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

        return;
}

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

        for (i = 1; i <= 10; i++) {
                InsertToFIFO(&head, &tail, i);
        }
        printf("FIFO List \r\n");
        PrintList(&head);

        return 0;
}

Makefile:
CC = gcc

CFLAGS = -g -Wall

all: queue_list
queue_list: queue_list.o
        ${CC} ${CFLAGS} -o $@ queue_list.o

clean:
        -@rm *.o

distclean: clean
         -@rm    queue_list

Output:
FIFO List
1
2
3
4
5
6
7
8
9
10

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

Middle Node 5

Find loop in the list and remove it

Following program to find the loop in the list and correct the loop

- Algorithm : loop through the list and return any node from the list

- Remove the loop :
Traverse the head and check if the looped node matches

#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;
}

void CreateLoopedList (struct node **head)
{
struct node *temp = *head;
struct node *merge = *head;

while (temp->next != NULL) {
temp = temp->next;
}
printf ("Created Loop Between Node\r\n == %d -> %d == \r\n", temp->data, (merge->next->next->next)->data);
temp->next = merge->next->next->next;

return;
}

void FindLoopInList (struct node **head, struct node **loopNode)
{
struct node *slow = NULL, *fast = NULL;

slow = fast = *head;

/* alternatively use visit flag
* to find loop node
* */
while (slow && fast) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
/* return any node in the loop
* where slow and fast ptr are met
**/
*loopNode = slow;
break;
}
}

return;
}

void RemoveLoopFromList (struct node **head, struct node *loopNode)
{
struct node *temp1 = *head;
struct node *temp2 = NULL;

while (*head) {
temp2 = loopNode;
/* start from head move temp1 for each looped node not found case
* keep move temp2 , unless looping node found
* temp1 traverse from head
* temp2 loop from looped one side node
* any point of time temp1 == temp2 then break
* **/
while (temp2->next != loopNode && temp2->next != temp1) {
temp2 = temp2->next;
}

if (temp2->next == temp1) {
/* found the loop, make next to null
**/
temp2->next = NULL;
return;
}

temp1 = temp1->next;
}

return;
}

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

for (i = 1; i <= 10; i++) {
AppendToList(&head, i);
}
printf("Head List \r\n");
PrintList(&head);

CreateLoopedList(&head);
FindLoopInList(&head, &loopNode);

RemoveLoopFromList(&head, loopNode);

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

return 0;
}

Makefile:

CC = gcc

CFLAGS = -g -Wall

all: mergenode findAndRemoveLoop

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

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

clean:
-@rm *.o

distclean: clean
-@rm mergenode
-@rm findAndRemoveLoop

Output:

Head List

Created Loop Between Node

== 1 -> 7 ==

After removing looped List

Find Intersect Node On Merged Linked List

Program to find intersect node in merged linked list

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

struct node {
int data;
int visited:1;
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->visited = 0;
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;
}

void MergeTwoList (struct node **head1, struct node **head2)
{
struct node *temp = *head1;
struct node *merge = *head2;

while (temp->next != NULL) {
temp = temp->next;
}
temp->next = merge->next->next->next;

return;
}

void FindIntersectNode (struct node **head1, struct node **head2, struct node **join)
{
struct node *temp = *head1;

while (temp->next != NULL) {
temp->visited = 1;
temp = temp->next;
}

temp = *head2;
while (temp->next != NULL) {
if (temp->visited) {
*join = temp;
return;
}
temp = temp->next;
}

return;
}

int main(void)
{
int i;
struct node *head1 = NULL, *head2 = NULL;
struct node *join = NULL;

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

for (i = 11; i <= 20; i++) {
AppendToList(&head2, i);
}

MergeTwoList(&head1, &head2);

printf("Merged Head1 List \r\n");
PrintList(&head1);

printf("Merged Head2 List \r\n");
PrintList(&head2);

FindIntersectNode(&head1, &head2, &join);

printf("Joined Node %d \r\n", join->data);

return 0;
}

CC = gcc

CFLAGS = -g -Wall

all: mergenode

mergenode: mergenode.o

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

clean:

-@rm *.o

distclean: clean

-@rm mergenode

Output:

Merged Head1 List

Merged Head2 List

Joined Node 17