Delete Alternate Nodes

Given a Singly Linked List, Delete all alternate nodes of the list ie delete all the nodes present in even positions.

Examples :

Input: LinkedList: 1->2->3->4->5->6
 
Output: 1->3->5

Explanation: Deleting alternate nodes ie 2, 4, 6 results in the linked list with elements 1->3->5.

Input: LinkedList: 99->59->42->20
 
Output: 99->42
 

Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)

Constraints:
1 <= number of nodes <= 10⁵
1 <= node->data <= 10³

Approach 01:

#include <iostream>
using namespace std;

class Solution {
public:
    void deleteAlt(Node* head) {
        Node* currentNode = head;
        Node* nextNode = nullptr;

        while (currentNode != nullptr && currentNode->next != nullptr) {
            // Store the next alternate node
            nextNode = currentNode->next;

            // Point the current node to the next alternate node
            currentNode->next = currentNode->next->next;

            // Delete the next node
            delete nextNode;

            // Move to the next node (which is now the next alternate node)
            currentNode = currentNode->next;
        }
    }
};

class Solution:
    def deleteAlt(self, head):
        currentNode = head

        while currentNode is not None and currentNode.next is not None:
            # Store the next alternate node
            nextNode = currentNode.next

            # Point the current node to the next alternate node
            currentNode.next = currentNode.next.next

            # Move to the next node (which is now the next alternate node)
            currentNode = currentNode.next

Time Complexity

• Iterating through the list:

  The function traverses the linked list and deletes every alternate node. Since it visits half of the nodes in the list, this takes \(O(n)\), where \(n\) is the number of nodes in the list.

• Deleting nodes:

  Each deletion operation takes \(O(1)\), and since the function performs these operations for half of the nodes, the total time spent on deletions is still \(O(n)\).

• Overall Time Complexity:

  The overall time complexity is \(O(n)\), where \(n\) is the number of nodes in the linked list.

Space Complexity

• Auxiliary Space:

  The function uses a constant amount of extra space for pointers such as currentNode and nextNode. No additional data structures are used, so the space complexity is \(O(1)\).

• Overall Space Complexity:

  The overall space complexity is \(O(1)\), as the function only uses a constant amount of extra space.