Author Archives: Raghavendar T S

Linked List in C – Check whether Linked List is Palindrome using Stack

Linked List in C - Check whether Linked List is Palindrome using Stack

Linked List in C – Check whether Linked List is Palindrome using Stack

DATA STRUCTURES IN C – LINKED LIST (20 PROGRAMS)

Linked List in C – Check whether Linked List is Palindrome using Stack :

Source Code :

#include<stdio.h>
struct node
{
    int data;
	    struct node *next;
};

void print(struct node **head)
{
    	struct node *temp=*head;
    	printf("\nList:");
    	while(temp!=NULL)
    	{
        		printf("\n%d ",temp->data);
        		temp=temp->next;		
    	} 
}

void push(struct node **stack_ptr,int data)
{
    	struct node *temp=*stack_ptr;
    	temp=(struct node*)malloc(sizeof(struct node));
    	temp->data=data;
    	temp->next=*stack_ptr;	
    	*stack_ptr=temp;
}

int palindrome(struct node **head)
{
    	struct node *temp=*head;
    	struct node *temp1=*head;
    	struct node *stack_ptr=NULL;

    	while(temp!=NULL)
    	{
        		push(&stack_ptr,temp->data);
        		temp=temp->next;		
    	}

    	while(temp1!=NULL)
    	{
        		if(temp1->data==stack_ptr->data)
        		{
            			temp1=temp1->next;
            			stack_ptr=stack_ptr->next;
            			continue;
        		}
        		else
        		{
            			printf("\nNot Palindrome");
            			return;
        		}				
    	}
    	printf("\nPalindrome");
}

int main()
{
    	struct node *one = (struct node*)malloc(sizeof(struct node));
    	struct node *two = (struct node*)malloc(sizeof(struct node));
    	struct node *three = (struct node*)malloc(sizeof(struct node));
    	struct node *four = (struct node*)malloc(sizeof(struct node));

    	struct node *head=one;

    	one->data=1;
    	one->next=two;

    	two->data=2;	
    	two->next=three;

    	three->data=2;
    	three->next=four;

    	four->data=1;
    	four->next=NULL;

    	print(&head);

    	palindrome(&head);	

    	return 0;
}

Output:

List:
1
2
2
1

Palindrome

Linked List in C- Check whether Linked List is Palindrome using Recursion

Linked List in C- Check whether Linked List is Palindrome using Recursion

Linked List in C- Check whether Linked List is Palindrome using Recursion

DATA STRUCTURES IN C – LINKED LIST (20 PROGRAMS)

Linked List in C- Check whether Linked List is Palindrome using Recursion :

Source Code :

#include<stdio.h>
struct node
{
    int data;
    	struct node *next;
};

void print(struct node **head)
{
    	struct node *temp=*head;
    	printf("\nList:");
	    while(temp!=NULL)
    	{
        		printf("\n%d",temp->data);
        		temp=temp->next;		
    	}
}

int palindrome(struct node **left,struct node *right)
{
    	if(right==NULL)
    	{
        		return 1;
    	}
    	int result=palindrome(left,right->next);
    	if(result==0)
    	{
        		return 0;
    	}
	    if((*left)->data==right->data)
	    {	
        		*left=(*left)->next;
        		return 1;
    	}
	    return 0;
}

int main()
{
    	struct node *one = (struct node*)malloc(sizeof(struct node));
    	struct node *two = (struct node*)malloc(sizeof(struct node));
    	struct node *three = (struct node*)malloc(sizeof(struct node));
    	struct node *four = (struct node*)malloc(sizeof(struct node));

    	struct node *head=one;

    	one->data=1;
    	one->next=two;

    	two->data=2;	
    	two->next=three;

    	three->data=2;
    	three->next=four;

    	four->data=1;
    	four->next=NULL;

    	print(&head);

    	int result=palindrome(&head,head);	

    	if(result==1)
    	{
        		printf("\nPalindrome");
    	}
    	else
    	{
        		printf("\nNot Palindrome");
    	}

    	return 0;
}

Output :

List:
1
2
2
1

Palindrome

Linked List in C- Reversing Every N Nodes of Linked List using Recursion

Linked List in C- Reversing Every N Nodes of Linked List using Recursion

Linked List in C- Reversing Every N Nodes of Linked List using Recursion

DATA STRUCTURES IN C – LINKED LIST (20 PROGRAMS)

Linked List in C- Reversing Every N Nodes of Linked List using Recursion :

Input: 1->2->3->4->5->6->7->8
Output: 3->2->1->6->5->4->8->7

Source Code :

#include<stdio.h>
struct node
{
    	int data;
    	struct node *next;
};

struct node* reverse(struct node **head,int N)
{
    	struct node *next;
    	struct node *prev=NULL;	
    	struct node *cur=*head;
    	int i=1;

    	struct node *holder=*head;

    	while(cur!=NULL && i<=N)
    	{
        		next=cur->next;
        		cur->next=prev;		
        		prev=cur;		
        		cur=next;
        		i++;			
    	}
    if(next!=NULL)
    {
        		holder->next = reverse(&next,N); 
    	}
    return prev;
}

void print(struct node **head)
{
    	struct node *temp=*head;
    	printf("\nList:");
	    while(temp!=NULL)
    	{
        		printf("\n%d ",temp->data);
        		temp=temp->next;		
    	}
}

int main()
{
    	struct node *one = (struct node*)malloc(sizeof(struct node));
    	struct node *two = (struct node*)malloc(sizeof(struct node));
    	struct node *three = (struct node*)malloc(sizeof(struct node));
    	struct node *four = (struct node*)malloc(sizeof(struct node));
    	struct node *five = (struct node*)malloc(sizeof(struct node));
    	struct node *six = (struct node*)malloc(sizeof(struct node));
    	struct node *seven = (struct node*)malloc(sizeof(struct node));
    	struct node *eight = (struct node*)malloc(sizeof(struct node));

    	struct node *head=one;

    	one->data=1;
    	one->next=two;

    	two->data=2;	
    	two->next=three;

    	three->data=3;
    	three->next=four;

    	four->data=4;
    	four->next=five;

    	five->data=5;	
    	five->next=six;

    	six->data=6;
    	six->next=seven;

    	seven->data=7;
    	seven->next=eight;

    	eight->data=8;
    	eight->next=NULL;

    	printf("\nBefore Reversing:");
    	printf("\nLinked List:");
    	print(&head);

    	head=reverse(&head,3);

    	printf("\nAfter Reversing:");
    	printf("\nLinked List:");
    	print(&head);	

    	return 0;
}

Output :

Before Reversing:
Linked List:
List:
1
2
3
4
5
6
7
8

After Reversing:
Linked List:
List:
3
2
1
6
5
4
8
7

Linked List in C – Detect/Find Loop

Linked List in C - Detect or Find Loop.png

Linked List in C – Detect/Find Loop

DATA STRUCTURES IN C – LINKED LIST (20 PROGRAMS)

Linked List in C – Detect/Find Loop :

           Loop in linked list is a situation where a node points to one of the previous node in the same linked list

Example:
Nodes: one->two->three->four->one->two->….
There are only four nodes in the linked list.
But the fourth node points to first node “one” which forms the loop.

Pseudo Code:

  1. Use 2 Pointers
    1. Pointer 1 – Fast Pointer
    2. Pointer 2 – Slow Pointer
  2. The fast pointer traversed twice the speed of slow pointer i.e. if slow pointer is traversed one node, the fast pointer should traverse two nodes
  3. Check whether the slow pointer and fast pointer are pointing same location
  4. If they are equal – Loop Found
  5. Else – Loop Not Found

If there is a loop in the linked list, the slow pointer and fast pointer will meet at some point of time

Source Code :

#include<stdio.h>

//Program to detect loop in the linked list
//Loop in linked list is a situation where a node points to one of the previous node in the same linked list
//
//one->two->three->four->one->two->....
//There are only four nodes in the linked list
//But the fourth node points to first node "one" which forms the loop
//
//Pseudo Code
//	Use 2 Pointers
//		Pointer 1-Fast Pointer
//		Pointer 2-Slow Pointer
//		The fast pointer traversed twice the speed of slow pointer i.e. if slow pointer is traversed one node, the fast pointer should traverse two nodes
//	Check whether the slow pointer and fast pointer are pointing same location
//	If they are equal
//		Loop Found
//	Else
//		Loop Not Found
//
//If there is a loop in the linked list, the slow pointer and fast pointer will meet at some point of time

struct node
{
    	//Structure named node to store integer in variable data and a pointer variable which can store address location of next node
    	int data;
    	struct node *next;
};

struct node *head=NULL;
//Declared as global variable since it is accessed by multiple functions

struct node* findloop()
{
    	//Function to detect whether loop is present in the linked list
    	struct node *slow_pointer=head;
    	struct node *fast_pointer=head;	
    	while(fast_pointer!=NULL)
	    {							
        		fast_pointer=fast_pointer->next;
        		//fast_pointer is traversed one node

        		if(fast_pointer!=NULL)
        		{
            			fast_pointer=fast_pointer->next;
            			//fast_pointer is traversed another node

            			slow_pointer=slow_pointer->next;
            			//slow_pointer is traversed one node
        		}

        		if(fast_pointer==slow_pointer)
        		{
            			//If there is a loop in the linked list, the slow pointer and fast pointer will meet at some point of time
            			printf("\nLoop Found");
            			return;
        		}		
    	}
    	printf("\nLoop Not Found");
}

void print()
{
    	//This funtion is used to print the data in each of the node in the linked list
    	//Process of moving from one node to another node is called as traversing
    	struct node *temp=head;
    	printf("\nList:");
    	while(temp!=NULL)
    	{
        		printf("\n%d ",temp->data);
        		temp=temp->next;		
    	}
}

int main()
{
    	struct node *one = (struct node*)malloc(sizeof(struct node));
    	struct node *two = (struct node*)malloc(sizeof(struct node));
    	struct node *three = (struct node*)malloc(sizeof(struct node));
    	struct node *four = (struct node*)malloc(sizeof(struct node));
    	//Four nodes are created

    	head=one;
    	//head pointer points to node one of the linked list

    	one->data=1;
    	one->next=two;

    	two->data=2;	
    	two->next=three;

    	three->data=3;
    	three->next=four;

    	four->data=4;
    	four->next=two;

    	//one->two->three->four->one->two->....
    	//There are only four nodes in the linked list
    	//But the fourth node points to first node "one" which forms the loop

    	//print();	
    	//Calling the print function will print the data in the nodes of the linked list infinitely

    	findloop();
    	//Calling the function findloop() to detect the presence of loop in the linked list

    	return 0;
}

Output :

Loop Found

Linked List in C – Detect/Find Loop

Linked List in C - Detect or Find Loop.png

Linked List in C – Detect/Find Loop

DATA STRUCTURES IN C – LINKED LIST (20 PROGRAMS)

Linked List in C – Detect/Find Loop :

           We use two pointers current and previous

Pseudo Code:
1. Current pointer initially points to first node(head) of the linked list
2. Previous node initially points to first node(head) of the linked list
3. We traverse current pointer from first node
4. For each node traversed in the linked list with current pointer, we again traverse the linked list from first node till where current pointer is pointing with previous pointer
5. Each time we check whether current node is pointing to previous node
6. If current node points to previous node Then
           Loop is present
Else
           Loop is not present

Source Code :

#include<stdio.h>

//We use two pointers current and previous
//
//Pseudo Code
//1. Current pointer initially points to first node(head) of the linked list
//2. Previous node initially points to first node(head) of the linked list
//3. We traverse current pointer from first node
//4. For each node traversed in the linked list with current pointer, we again traverse the linked list from first node till where current pointer is pointing with previous pointer
//5. Each time we check whether current node is pointing to previous node
//6. If current node points to previous node Then
//		Loop is present
//	Else
//		Loop is not present

struct node
{
    	//Structure named node to store integer in variable data and a pointer variable which can store address location of next node
	    int data;
    	struct node *next;
};

struct node *head=NULL;
//Declared as global variable since it is accessed by multiple functions

struct node* findloop()
{
    	//Function to detect whether loop is present in the linked list

    	struct node *current=head;

    	while(current->next!=NULL)
    	{
        		struct node *previous=head;

        		while(previous!=NULL && previous!=current)
        		{
            			if(current->next ==previous)
            			{
                				printf("Loop Found");
                				return;
            			}
            			previous=previous->next;
        		}
        	current=current->next;
    	}
    	printf("\nLoop Not Found");
}

void print()
{
    	//This funtion is used to print the data in each of the node in the linked list
    	//Process of moving from one node to another node is called as traversing
    	struct node *temp=head;
    	printf("\nList:");
    	while(temp!=NULL)
    	{
        		printf("\n%d ",temp->data);
        		temp=temp->next;		
    	}
}

int main()
{
    	struct node *one = (struct node*)malloc(sizeof(struct node));
    	struct node *two = (struct node*)malloc(sizeof(struct node));
    	struct node *three = (struct node*)malloc(sizeof(struct node));
    	struct node *four = (struct node*)malloc(sizeof(struct node));
    	//Four nodes are created

    	head=one;
    	//head pointer points to node one of the linked list

    one->data=1;
    	one->next=two;

    	two->data=2;	
    	two->next=three;

    	three->data=3;
    	three->next=four;

    	four->data=4;
    	four->next=one;
    	//one->two->three->four->one->two->....
    	//There are only four nodes in the linked list
    	//But the fourth node points to first node "one" which forms the loop

    	//print();	
    	//Calling the print function will print the data in the nodes of the linked list infinitely	

    	findloop();
    	//Calling the function findloop() to detect the presence of loop in the linked list

    	return 0;
}

Output :

Loop Found