Delete Alternate Nodes

Problem

Given a Singly Linked List of size n, delete all alternate nodes of the list.

Examples:

Example 1:

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

Example 2:

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

Your task:

Your task is to complete the function deleteAlt() which takes the head of the linked list in the input parameter and modifies the given linked list accordingly.

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

Constraints:

• $1<=n<=10^5$
• $1<=node.data<=10^6$

Solution

Python

def deleteAlt(self, head):
    if (head == None):
        return
    prev = head 
    now = head.next
    while (prev != None and now != None): 
        prev.next = now.next
        now = None
        prev = prev.next
        if (prev != None): 
            now = prev.next

Java

public void deleteAlternate (Node head){
    if (head == null)
        return;
    Node node = head;
    while (node != null && node.next != null) {
        node.next = node.next.next;
        node = node.next;
    }
}

C++

void deleteAlt(struct Node *head){
    if (head == NULL) 
        return
    Node *prev = head; 
    Node *node = head->next; 
    while (prev != NULL && node != NULL) {
        prev->next = node->next; 
        delete(node); 
        prev = prev->next; 
        if (prev != NULL) 
            node = prev->next; 
    } 
}

C

void deleteAlt(struct Node *head) {
    if (head == NULL) 
        return;
    struct Node *prev = head; 
    struct Node *node = head->next; 
    while (prev != NULL && node != NULL) {
        prev->next = node->next; 
        free(node); 
        prev = prev->next; 
        if (prev != NULL) 
            node = prev->next; 
    } 
}

• Time Complexity: $O(n)$
• Auxiliary Space: $O(1)$