Delete Alternate Nodes of a Linked List

Introduction

A Linked List is a container called a data structure that stores the elements at non-contiguous memory locations. It works with the help of the next pointer. Each node has a next pointer that holds the address of the next node. To understand Linked List, visit our site, Linked List | Learn & Practice from Coding Ninjas Studio. 

Delete Alternate Nodes of a Linked List

The problem is removing or deleting the alternate occurring nodes of a Linked List. Suppose you are given a linked list 7->5->3->1, then after removing the alternate nodes from the second node, you would get 7 -> 3. Also, if you are given 1->2->3->4->5->6->7, then the output after removing alternate nodes would be 1->3->5->7. 

The steps of implementation to solve the above problem are:

1. Create a struct variable node that has data and a next pointer.
    
2. Initialize the linked list by setting the head variable to NULL, indicating an empty list.
    
3. Write an insert method to insert elements or nodes in the list. ‘
    
4. Write a delete function to remove alternate elements from the list. This function will iterate through the list and skips one item, and delete every other alternating item from the list.
    
5. Write a function to display the elements of the list at any time to print output and verify results. 

C++ Implementation

#include<iostream>
using namespace std;

/* Declaring Struct variable Node to represent a node in the Linked List. */
struct Node {
    int data;
    Node *next;
};

/* A function to delete alternative nodes from the Linked List */
void DeleteAlternativeNodes(Node *head) {
    /* Check for empty List*/
    if(head == NULL)
        return;
     
    Node *current_node = head;
    Node *next_node = head->next;
   
    /* Loop to iterate over the complete list*/
    while(next_node != NULL && current_node != NULL){
        current_node ->next = next_node->next;
       
        /* Removing the alternative node*/
        free(next_node);
       
        /*Updating current_node*/
        current_node  = current_node ->next;
        if (current_node  != NULL) {
        next_node = current_node ->next;
        }
    }
}

/* A function to display the given linekd list*/
void DisplayLinkedList(Node *node) {
   
    /* Loop to iterate over the list and printing each element*/
    while (node != NULL) {
        cout << node->data;
        node = node->next;
       
        if(node != NULL)
            cout<<" -> ";
    }
}

/* An insert function to insert an item with value temp_data in the Linked list*/
void NodeInsert(Node** head_ref, int temp_data) {
    Node* temp_node = new Node();
    temp_node->data = temp_data;
    temp_node->next = (*head_ref);
    (*head_ref) = temp_node;
}

/* Driver function*/
int main() {
   
    /* Initializing an empty Linked List*/
    Node* head = NULL;
   
    /* Inserting Sample elements*/
    NodeInsert(&head, 5);
    NodeInsert(&head, 4);
    NodeInsert(&head, 3);
    NodeInsert(&head, 2);
    NodeInsert(&head, 1);
   
    /* Displaying nodes before deletion*/
    cout << "Before Deletion:\n";
    DisplayLinkedList(head);
   
    DeleteAlternativeNodes(head);
   
    /* Displaying nodes after deletion*/
    cout << "\nAfter Deletion:\n";
    DisplayLinkedList(head);
   
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Before Deletion:
1 -> 2 -> 3 -> 4 -> 5
After Deletion:
1 -> 3 -> 5

Time complexity

O(n), where n denotes the number of nodes in the linked list.

Reason: To remove the alternate nodes of a Linked list, we must iterate through the entire list. Hence, the complexity of O(n) for n nodes.

Space complexity

O(n), where n denotes the number of nodes in the linked list.

Reason: To store the list elements, we require O(n) space complexity. Other than the list itself, the space required is constant.