DATA STRUCTURES IN C – LINKED LIST (20 PROGRAMS)
Linked List in C – Split a Linked List into 2 Separate Linked List :
Input:
Head Pointer: head
Original linked list: node 1->node 2->node 3->node 4->node 5->node 6->node 7
Output:
Head Pointer: head_of_list_1
Linked List 1: node 1->node 3->node 5->node 7
Head Pointer: head_of_list_2
Linked List 2: node 2->node 4->node 6
Source Code :
#include<stdio.h> 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 struct node *head_of_list_1 = NULL; struct node *head_of_list_2 = NULL; //Pointer head_of_list_1 and head_of_list_2 i used to store the starting node of the two output linked list //Declared as global variable since it is accessed by multiple functions void split_the_linked_list() { //Function to split a linked list into two seperate linked list //If the original list is 1->2->3->4->5->6, then the the first linked list will contain nodes 1->3->5(outputlinked list 1) // the seconf linked list will contain nodes 2->4->6(outputlinked list 2) struct node *temp = head; //Use a new pointer variable temp //Do not use the pointer variable head directly. If we use it, the address location of the first node in the linked list will be lost struct node *listholder1 = NULL; struct node *listholder2 = NULL; //listholder1 and listholder2 are temporary pointer variables to store the address of last node of two output linked list struct node *ptr; int i=1; while(temp!=NULL) { //Loop to traverse the original linked list if(i%2==1) { //Executed for nodes with odd index of nodes i.e. for nodes 1,3,5 etc of the original input linked list ptr = (struct node*)malloc(sizeof(struct node)); //A new node is created ptr->data=temp->data; ptr->next=NULL; //The newly created node is assigned the data from the node of original list if(head_of_list_1==NULL) { //Executed only once when the the pointer head_of_list_1 is empty head_of_list_1=ptr; } else { listholder1->next=ptr; //listholer1 is used to identify the last node of output linked list 1 //Once a new node is created we need to make listholder1 point to newly created node } listholder1=ptr; //Making the newly created node as last node } else { //Executed for nodes with even index of nodes i.e. for nodes 2,4,6 etc of the original input linked list //Other statements are same as above except that we use head_of_list_2 and listholder2 to maintain output linked list 2 ptr = (struct node*)malloc(sizeof(struct node)); ptr->data=temp->data; ptr->next=NULL; if(head_of_list_2==NULL) { head_of_list_2=ptr; } else { listholder2->next=ptr; } listholder2=ptr; } temp=temp->next; i++; } } 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 head=one; //head pointsto 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=five; five->data=5; five->next=six; six->data=6; six->next=seven; seven->data=7; seven->next=NULL; //Last node of input linked list //one->two->three->four->five->six->seven split_the_linked_list(); //Function to split the input linked list into two output linked list printf("\nOriginal Linked List/Input Linked List"); print(head); //Printnig original linked list/input linked list printf("\nOutput:Linked List 1"); print(head_of_list_1); //Printnig output linked list 1 printf("\nOutput:Linked List 2"); print(head_of_list_2); //Printnig output linked list 2 return 0; }
Output :
Original Linked List/Input Linked List 1 2 3 4 5 6 7 Output:Linked List 1 1 3 5 7 Output:Linked List 2 2 4 6