Author Archives: Raghavendar T S

Linked List in C- Merge two Linked List into Single Linked List – Efficient

Linked List in C- Merge two Linked List into Single Linked List - Efficient

Linked List in C- Merge two Linked List into Single Linked List – Efficient

DATA STRUCTURES IN C – LINKED LIST (20 PROGRAMS)

Linked List in C- Merge two Linked List into Single Linked List – Efficient :

Input
Linked List 1: one->three->five->seven
Head of Linked List 1 is head1

Linked List 2: two->four->six
Head of Linked List 2 is head2

Output
Linked List 3: one->two->three->four->five->six->seven

Head of Linked List 3 is head1

This program works irrespective of size of the two input linked list.

Source Code :

#include<stdio.h>

	//Input
	//Linked List 1: one->three->five->seven
	//Head of Linked List 1 is head1 
	//
	//Linked List 2: two->four->six
	//Head of Linked List 2 is head2
	//
	//Output
	//Linked List 3: one->two->three->four->five->six->seven
	//Head of Linked List 3 is head1

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;
    	//Pointer variable next is a self referential pointer which stores the address of structure node
};

struct node *head1 = NULL;
struct node *head2 = NULL;
//Pointer head1 and head2 are the pointers which stores the address of two input linked list

void merge()
{
    	//Function to merge the two input linked list
    	struct node *temp1 = head1;
    	struct node *temp2 = head2;
    	//Use a new pointer variable temp1 and temp2
    	//Do not use the pointer variable head1 and head2 directly. If we use it, the address location of the first node in the two linked list will be lost

    	struct node *holder1 = NULL;
    	struct node *holder2 = NULL;
    	//Temporary pointer variables to store the address of next node of the two input linked list

    	while(temp1!=NULL && temp2!=NULL)	
    	{
	        	//Executes until both temp1 and temp2 are not NULL

        		holder1=temp1->next;
        		//Storing the address of next node of first linked list

        		temp1->next=temp2;
        		//Making the first node of first linked list point to first node of second linked list

        		if(holder1!=NULL)			
        		{
            			//Making the first node of second linked list point to second node of first linked list
            			holder2=temp2->next;
            			temp2->next=holder1;
		        }							
        		temp1=holder1;
        		temp2=holder2;	
        		//Updating the address location of two pointer variables temp1 and temp2
    	}
}

void print(struct node *temp)
{
    	//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
    	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));
    	//Seven nodes are created

    	head1=one;
    	head2=two;
    	//head1 points to first node of first linked list
    	//head2 points to first node of second linked list

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

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

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

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

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

    	six->data=6;
    	six->next=NULL;
    	//Last node of second input linked list

    	seven->data=7;
    	seven->next=NULL;
    	//Last node of first input linked list

    	//Input
    	//Linked List 1: one->three->five->seven
    	//Head of Linked List 1 is head1 
    	//
    	//Linked List 2: two->four->six
    	//Head of Linked List 2 is head2
    	//
    	//Output
    	//Linked List 3: one->two->three->four->five->six->seven
	    //Head of Linked List 3 is head1

    	printf("\nBefore Merging");
    	printf("\nInput: Linked List 1");
    	print(head1);

    	printf("\nInput: Linked List 2");
    	print(head2);

    	merge();
    	//Merging the two linked list into single linked list

    	printf("\nAfter Merging");
    	printf("\nOutput: Linked List 3");
    	print(head1);

    	return 0;
}

Output :

Before Merging
Input: Linked List 1
// Head pointer of first linked list is head1
1
3
5
7

Input: Linked List 2
// Head pointer of second linked list is head2
2
4
6

After Merging
Output: Linked List 3
// Head pointer of output linked list is head1
1
2
3
4
5
6
7

Linked List in C- Reversing a Linked List

Linked List in C- Reversing a Linked List

Linked List in C- Reversing a Linked List

DATA STRUCTURES IN C – LINKED LIST (20 PROGRAMS)

Linked List in C- Reversing a Linked List :

Input:
Linked List: one->two->three->four
head pointer points to first node “one”

Output:
Linked List: four->three->two->one
head pointer points to first node “four”

Source Code :

#include<stdio.h>

	//Input:
	//	Linked List: one->two->three->four
	//	head pointer points to first node "one"
	//
	//Output:	
	//	Linked List: four->three->two->one
	//	head pointer points to first node "four"

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;
    	//Pointer variable next is a self referential pointer which stores the address of structure node
};

struct node *head=NULL;
//Pointer head is used to store the starting node of the input linked list

void reverse()
{
    	//Function to reverse a linked list

    	struct node *next;
    	//Pointer to store the address of next node of current node
	    //current or cur pointer is the pointer with which we are traversing the linked list

    	struct node *prev=NULL;
    	//prev pointer stores the address of previous node of current node

    	struct node *cur=head;
    	//cur or Current pointer initially points to first node in the linked list

	    while(cur!=NULL)
    	{
        		next=cur->next;
		        //Storing the address of next node of the current node

        		cur->next=prev;
        		//Making the current node point to previous node

        		prev=cur;
        		//Making current node as previous node

        		cur=next;
        		//Making next node as current node
    	}
    	head=prev;
	    //Initially head points to first node in the linked list
	    //So we are now making the head point to last node in the linked list
}

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));
    	//Creating 4 nodes

    	head=one;
    	//head points to node one of input 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=NULL;
    	//End of linked list

    	//Linked List: one->two->three->four
    	//head pointer points to first node "one"

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

    	reverse();
    	//Calling the reverse function

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

    	return 0;
}

Output :

Before Reversing:
Linked List:
List:
1
2
3
4

After Reversing:
Linked List:
List:
4
3
2
1

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