How to delete alternate nodes in a linked list

A linked list is a common data structure made up of one or more than one nodes. Each node contains a value and a pointer to the next node forming a chain-like structure. These nodes are stored randomly in the system's memory, which improves its space complexity compared to the array.

Understanding the problem

We get a linked list in which we want to remove all the alternate nodes from a list that begins with the same head node. We need to remove all the alternate nodes from the given list. Let's visualize it in the illustration below:

//fuction for deleting alternate nodes
void deleteAlternate(node *head_ptr) 
{ 
    if (head_ptr == NULL) 
        return; 
     //Initialize prev and current node
    node *current = head_ptr;
    node *previous = head_ptr->link;
     
    while (current != NULL && previous != NULL) 
    { 
        current->link = previous->link; //updating address link
        delete(previous); // delete the node
        current = current->link; //updating current node
        if (current != NULL) 
            previous = current->link; 
    } 
} 
int main(){
  node* list1=new node();  
	list1 = NULL;
  list1=add_node(list1,0);
  add_node(list1,2);
  add_node(list1,4);
  add_node(list1,6);
  add_node(list1,8);
  
  cout << "Linked List: ";
  print_data(list1);
  
  deleteAlternate(list1);
  cout<<"\nAfter deletion: ";
  print_data(list1);
  
}

Explanation

Lines 1–5: We define the deleteAlternate function in which we delete alternate nodes. First, we check if the list is empty, and return NULL .
Lines 7–13: We initialize the nodes—prev and current to keep track of nodes. After updating the link of the current node, we delete the previous node.
Lines 15–19: We update the value of the current node for the next iteration.

Time complexity: The time complexity for this approach is $O(n)$ where $n$ is the number of nodes in the given linked list.

Space complexity: The space complexity for this approach is $O(1)$ .

Recursive solution

The approach above is simple but not efficient. We can also solve this problem efficiently by using recursion. Despite being short and simple, the recursive code requires $O(n)$ calls to recursive functions when dealing with a linked list of length $n$ . Let's see its step-by-step implementation:

// function to alternate nodes
void deleteAlternate(node *head_ptr) 
{ 
    if (head_ptr == NULL) 
        return; 
  
    node *current_node = head_ptr->link; //pointer to next node 
  
    if (current_node == NULL) 
        return; 
  
    head_ptr->link = current_node->link; //changing next node 
      
    delete(current_node); // delete node
  
    deleteAlternate(head_ptr->link); //recursively calling for each node
} 
int main(){
  node* list1=new node();  
  list1 = NULL;
  list1=add_node(list1,0);
  add_node(list1,2);
  add_node(list1,4);
  add_node(list1,6);
  add_node(list1,8);
  
  cout << "Linked List: ";
  print_data(list1);
  
  deleteAlternate(list1);
  cout<<"\nAfter deletion: ";
  print_data(list1);
  
}

Explanation

Lines 1–5: We define the deleteAlternate function in which we delete alternate nodes. First, we check if the list is empty, and return NULL.
Lines 7–12: We initialize the current node to keep track of nodes. After updating the link of the current node, we check if it is NULL.
Lines 14–17: We delete the current node for the next iteration. We call deleteAlternate recursively until we reach the NULL pointer.

Time complexity: The time complexity for this approach is $O(n)$ where $n$ is the number of nodes in the given linked list.

Space complexity: The space complexity for this approach is $O(1)$ .

Free Resources

How to delete alternate nodes in a linked list

Understanding the problem

Simple solution

Explanation

Recursive solution

Explanation