Delete Alternate Nodes Of A Linked List

Problem Statement

Given a singly linked list. Remove its alternate nodes.

Example
Sample Input: 3->5->2->6->8
Sample Output: 3->2->8

Here 5 and 6 were the nodes at alternate positions. So, we have removed them.

Sample Input: 3->5->2->6->8->7
Sample Output: 3->2->8

Here 5, 6, and 7 were nodes at alternate positions. So, we have removed them.

Problem Statement Understanding

In this problem, we have to delete alternate nodes of the given linked list. Deleting alternate nodes means deleting nodes at alternate positions in the linked list.

Let’s understand this:
Consider a linked list 3->5->2->6->8->7 and lets mark the positions of the node (Using 1 based indexing).

If we start from position 1, the alternate nodes are at positions 2, 4, and 6.

Can you observe something about the alternate positions?
Now, hopefully i think it is clear what we have to do in this problem.

Approach (Iterative)

I hope you have understood the problem and have got a basic idea of what we are going to do.

We can observe from the above example that the alternate positions are the positions that are even. So, deleting alternate nodes becomes deleting nodes at even positions in the linked list. To do so, the idea is simple, while iterating through the linked list we need to keep a track of the node’s position and a pointer to the previous node. After reaching an even position, we just need to remove that node from the linked list and move ahead.

Since it is clear what we need to do, take some time and think about how we are going to do it. Below is the algorithm explaining the steps we need to take to implement our idea.

Algorithm

  • Declare three variables: ‘curr’, ‘position’ and ‘prev’.
  • Initialize position as 1 and prev as ‘NULL’ and ‘curr’ to head.
  • Iterate through the linked list using curr and update positions and prev.
  • If we reach an even position, delete the node at that position from the linked list by connecting the previous node to the next node of curr and deleting the current node, and move ahead.

Dry Run

Code Implementation:


#include
using namespace std;

struct Node {
    int val;
    Node* next;

    Node(int value){
        val = value;
        next = NULL;
    }
};

void push_front(Node** head, int new_val){
    Node* new_node = new Node(new_val);
    new_node->next = *head;
    *head = new_node;
}

void printList(Node* head){
    Node* i = head;
    while(i){
        cout<val<<" ";
        i = i->next;
    }
    cout<<"\n";
}

void delete_alt_nodes(Node* head){
    
    int position = 1;
    Node *prev = NULL;
    
    Node *curr = head;
    while(curr != NULL){
        if(position%2==0){
            // delete curr
            prev->next = curr->next;
            Node *temp = curr;
            curr = curr->next;
            delete temp;
        }
        else {
            prev = curr;
            curr = curr->next;
        }
        position ++;
    }
}

int main(){
    Node* head = NULL;
    push_front(&head, 8);
    push_front(&head, 6);
    push_front(&head, 2);
    push_front(&head, 5);
    push_front(&head, 3);
    
    cout<<”Original list:\n”;
    printList(head);
    // 3 5 2 6 8

    delete_alt_nodes(head);
    
    cout<<”After deleting alternate nodes:\n”;
    printList(head);
    // 3 2 8
}

Output

Original list:
3 5 2 6 8

After deleting alternate nodes:
3 2 8

Time complexity: O(n), where n is the number of nodes in the linked list.

Space complexity: O(1), since we don’t use any extra space.

I hope you have understood the iterative approach. Now, let’s see another way to approach the problem.

Approach (Recursive)

We already know what deleting alternate nodes of a linked list means.

If we start from the first node we delete the second node and fourth node and so on. Given a linked list with at least 2 nodes and a given pointer to the first node we can easily delete the second node by making the ‘next’ of the first node as next of the first. Deleting the fourth node would be the same if we consider the linked list starting from the third node. Then the node to delete would be the 2nd node in that linked list.

Here we broke the given problem into a smaller problem. We delete the second node from the given linked list and call the same function for the linked list starting from the third node.

Now, what will be the base case?
If the linked list is empty or has only one node, we don’t have a second node to delete. So, we simply return the passed linked list.

Now that you have understood the approach, try to implement this idea yourself.

Algorithm

  • If the linked list is empty or has only one node, return the linked list. (Base case)
  • Store the pointer to the second node in a variable ‘second’ as: second = head->next.
  • Recursively call the same function for the linked list after the 2nd node and store the linked list returned as ‘rem’.
  • Attach this linked list pointed by ‘rem’ to the first node as: head->next = rem
  • Now the second node is disconnected from the linked list, so delete it using the delete command.
  • Return the resulting linked list.

Dry Run

Code Implementation:


#include
using namespace std;

struct Node {
    int val;
    Node* next;

    Node(int value){
        val = value;
        next = NULL;
    }
};

void push_front(Node** head, int new_val){
    Node* new_node = new Node(new_val);
    new_node->next = *head;
    *head = new_node;
}

void printList(Node* head){
    Node* i = head;
    while(i){
        cout<val<<" ";
        i = i->next;
    }
    cout<<"\n";
}

// recursive function to delete alternate nodes of a linked list
Node* delete_alt(Node* head){
    // base case
    if(head==NULL || head->next==NULL) return head;

    Node* second = head->next;
    Node* rem = delete_alt(second->next);
    head->next = rem;

    delete second;

    return head;
}

int main(){
    Node* head = NULL;

    push_front(&head, 8);
    push_front(&head, 6);
    push_front(&head, 2);
    push_front(&head, 5);
    push_front(&head, 3);

    printList(head);
    // 3 5 2 6 8

    delete_alt(head);

    printList(head);
    // 3 2 8
}

Output

Original list:
3 5 2 6 8

After deleting alternate nodes:
3 2 8

Space Complexity: O(n), due to function call stack, where n is the number of nodes in the linked list.

Through this article, we learned how to delete alternate nodes of a linked list. Problems like these are good for strengthening your concepts in LinkedList. I would highly recommend you to practice more such problems from Linked List.

Previous post Doubly Circular Linked List – Deletion
Next post Circular Linked List – Insertion

Leave a Reply

Your email address will not be published. Required fields are marked *