C Program to delete alternate nodes of a Linked List

Delete alternate nodes of a Linked List

C Program to delete alternate nodes of a Linked List. In this program, we want to remove alternate nodes from the singly linked list which is start from the second node of the linked list and remove all the alternate nodes of it.

For Example,

  • Input: 1 -> 3 -> 5 -> 7 -> 9
  • Output: 1 -> 5 -> 9 
nodes

Structure of creating a node of the singly linked list:-

struct node
{
    int data;
    struct node *next;
};
C Program to delete alternate nodes of a Linked List

Working for deleting alternate nodes of a Singly Linked List:-

  • Take linked list input
  • Initialize prev and curr, assign prev = head & curr = head->next
  • Change next pointer of previous to curr->next, so link between prev & curr is broken
  • Now, curr is unreachable, free its memory
  • Move prev to next node in linked list
  • Move curr to next node.
  • Keep doing all above steps until you reach end of the node

C Program to delete alternate nodes of a Linked List –

#include<stdio.h>
#include<stdlib.h>

//Structure of node 
struct Node
{
    int data;
    struct Node *next;
};

//display the nodes
void display(struct Node* node){

    //as linked list will end when Node is Null
    while(node!=NULL)
    {
        printf("%d ",node->data);
        node = node->next;
    }
    printf("\n");
}

void insert(struct Node** head, int data){

    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));

    newNode->data = data;
    newNode->next = *head;

    //changing the new head to this freshly entered node
    *head = newNode;
}

// function to delete alternate nodes
void delete_Alt(struct Node *head)  
{
    if (head == NULL)
        return;
  
    // prev req so its next node can be changed
    struct Node *prev = head;
    struct Node *curr = head->next;
  
    while (prev != NULL && curr != NULL)
    {
        // changing next of previous node
        prev->next = curr->next;
  
        // free the memory
        free(curr);
  
        // Update prev and curr 
        prev = prev->next;
        if (prev != NULL)
            curr = prev->next;
    }
}
int main()
{
    struct Node *head = NULL;
    
    insert(&head,1);
    insert(&head,2);
    insert(&head,3);
    insert(&head,4);
    insert(&head,5);
    
    printf("Before deletion: ");
    display(head);
    
    delete_Alt(head);
    
    printf("After deletion: ");
    display(head);
    return 0;
}

Output

Before deletion: 5 4 3 2 1 
After deletion: 5 3 1

Above has a time complexity of O(N)

Now let us look at the recursive approach for the same.

Method 2 (using Recursion)

Below also has O(N) time complexity due to n order recursive calls.

#include 
#include

//Structure of node 
struct Node
{
    int data;
    struct Node *next;
};

//display the nodes
void display(struct Node* node){

    //as linked list will end when Node is Null
    while(node!=NULL)
    {
        printf("%d ",node->data);
        node = node->next;
    }
    printf("\n");
}

void insert(struct Node** head, int data){

    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));

    newNode->data = data;
    newNode->next = *head;

    //changing the new head to this freshly entered node
    *head = newNode;
}

// function to delete alternate nodes
void delete_Alt(struct Node *curr)
{
    if (curr == NULL)
        return;
    
    // assigning node to current node's next
    struct Node *del_node = curr->next;
  
    if (del_node == NULL)
        return;
  
    // changing next node of curr to alternative node
    // del_node is no more part of Linked List
    curr->next = del_node->next;
  
    // memory for del_node also freed
    free(del_node);
  
    // Recursively call for the new next of curr
    delete_Alt(curr->next);
}
int main()
{
    struct Node *head = NULL;
    
    insert(&head,1);
    insert(&head,2);
    insert(&head,3);
    insert(&head,4);
    insert(&head,5);
    
    printf("Before deletion: ");
    display(head);
    
    delete_Alt(head);
    
    printf("After deletion: ");
    display(head);
    return 0;
}

Output

Before deletion: 5 4 3 2 1 
After deletion: 5 3 1