Delete alternate nodes in a linked list

In the given singly linked list, delete all the alternate nodes starting from the second node in the linked list

Example

Input linked list

Output will be

Algorithm

Time complexity : O(n)

Step 1: create a function which takes the head of the linked list and outputs the linked list after deleting all the alternate nodes starting from the second node.
Step 2 : In this function,
a)    Create a dummy node temp to traverse in the linked list.
b)    Store head pointer in the temp.
Step 3 : run a loop till the current node has a next.
In the loop
a)    Create a variable “t” store the next of current node.
b)    Change next of current node to next of t
c)    Delete t node.
d)    And move the pointer of current node.
This deletes all the alternate nodes staring from second node.
Step 4 : call the function on the given input linked list. It deletes all the alternate nodes.

Algorithm working Example

C++ Program

#include <bits/stdc++.h>
using namespace std;

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


void insertAtBeginning(struct LL**head,int dataToBeInserted)
{
	struct LL* curr=new LL;
		
		curr->data=dataToBeInserted;
		curr->next=NULL;
	
	if(*head==NULL)
			*head=curr; //if this is first node make this as head of list
		
	else
		{
			curr->next=*head; //else make the current (new) node's next point to head and make this new node a the head
			*head=curr;
		}
		
		//O(1) constant time
}

void deleteAlternateNode(struct LL **head)
{
	struct LL *temp = *head , *t; 
	
	while(temp and temp->next)
	{
		t = temp->next;
		temp->next = t->next;
		delete(t);
		
		temp = temp->next;
	}
	
}

void display(struct LL**head)
{
	struct LL*temp=*head;
	while(temp!=NULL)
		{
			if(temp->next!=NULL)
			cout<<temp->data<<" ->";
			else
			cout<<temp->data;
			
			temp=temp->next; //move to next node
		}
		//O(number of nodes)
	cout<<endl;
}


int main()
{
	
	struct LL *head = NULL; //initial list has no elements
	insertAtBeginning(&head,6);
	insertAtBeginning(&head,16);
	insertAtBeginning(&head,15);
	insertAtBeginning(&head,50);
	insertAtBeginning(&head,1);
	insertAtBeginning(&head,23);
	cout<<"Current List is :-\n";
	display(&head);
	
	deleteAlternateNode(&head); //Last node deletion
	
	cout<<"\n After deleting alternate nodes the list becomes \n";
	display(&head);
	
	return 0;
}
Try It


Next > < Prev
Scroll to Top