Linked List in C- Split a Linked List into 2 Linked List

Linked List in C- Split a Linked List into 2 Linked List

Linked List in C- Split a Linked List into 2 Linked List

DATA STRUCTURES IN C – LINKED LIST (20 PROGRAMS)

Linked List in C- Split a Linked List into 2 Linked List :

Input:
        Head Pointer: head1
        Original linked list: node 1->node 2->node 3->node 4->node 5->node 6->node 7

Output:
        Head Pointer: head1
        Linked List 1: node 1->node 3->node 5->node 7

        Head Pointer: head2
        Linked List 2: node 2->node 4->node 6

Source Code :

#include<stdio.h>
///////////////////////////////////////////////////////////////////////////////////////////
//Input:
//        Head Pointer: head1
//        Original linked list: node 1->node 2->node 3->node 4->node 5->node 6->node 7
//
//Output:
//        Head Pointer: head1
//        Linked List 1: node 1->node 3->node 5->node 7
//
//        Head Pointer: head2
//        Linked List 2: node 2->node 4->node 6
///////////////////////////////////////////////////////////////////////////////////////////

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;
void split()
{
	    int i=0;

	    struct node *temp=head1;
    	head2=temp->next;
    	//one->two->three->four->five->six->seven
    	//Making the pointer head1 point to node "one"
    	//Making the pointer head2 point to node "two"

    	struct node *holder1=head1;
    	struct node *holder2=head2;
    	//Temporary pointer to store address of previous node

    	while(temp!=NULL)
    	{
        		i++;
        		if(i%2==1 && i!=1)
        		{			
            			//Not executed for i=1
            			holder1->next=temp;
            			holder1=holder1->next;
        		}
        		if(i%2==0 && i!=2)		
        		{
            			//Not executed for i=2
            			holder2->next=temp;
            			holder2=holder2->next;
        		}
        		temp=temp->next;
	    }
    	holder1->next=NULL;
    	holder2->next=NULL;
	    //Making the last nodes of two linked list with head pointer "head1" and "head2" point to NULL
}

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;
    	//head1 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=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

    	printf("\nLinked List:Before Splitting");
    	print(head1);
    	//Before split function is executed , Linked list with head pointer "head1" has 7 nodes

    	split();
    	//Function to split a linked list into two linked list

    	printf("\nLinked List:After Splitting");
    	printf("\nOutput:Linked List 1");
    	print(head1);
    	//After split function is executed , Linked list with head pointer "head1" has nodes with odd index

    	printf("\nOutput:Linked List 2");
    	print(head2);
    	//After split function is executed , Linked list with head pointer "head2" has nodes with even index

    	return 0;
}

Output :

Linked List:Before Splitting
//Input Linked List
//Head Pointer is head1
1
2
3
4
5
6
7

Linked List:After Splitting
Output:Linked List 1
//Head Pointer is head1
1
3
5
7

Output:Linked List 2
//Head Pointer is head2
2
4
6

[ YOU MAY ALSO LIKE ]

Leave a Reply