Given a Singly Linked List, starting from the second node delete all alternate nodes of it. For example, if the given linked list is 1->2->3->4->5 then your function should convert it to 1->3->5, and if the given linked list is 1->2->3->4 then convert it to 1->3.
Method 1 (Iterative):
Keep track of previous of the node to be deleted. First, change the next link of the previous node and iteratively move to the next node.
C++
// C++ program to remove alternate // nodes of a linked list #include <bits/stdc++.h>using namespace std;// A linked list node class Node { public: int data; Node *next; }; /* Deletes alternate nodes of a list starting with head */void deleteAlt(Node *head) { if (head == NULL) return; /* Initialize prev and node to be deleted */ Node *prev = head; Node *node = head->next; while (prev != NULL && node != NULL) { /* Change next link of previous node */ prev->next = node->next; // Update prev and node prev = prev->next; if (prev != NULL) node = prev->next; } } /* UTILITY FUNCTIONS TO TEST fun1() and fun2() *//* Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list. */void push(Node** head_ref, int new_data) { /* Allocate node */ Node* new_node = new Node(); /* Put in the data */ new_node->data = new_data; /* Link the old list of the new node */ new_node->next = (*head_ref); /* Move the head to point to the new node */ (*head_ref) = new_node; } /* Function to print nodes in a given linked list */void printList(Node *node) { while (node != NULL) { cout << node->data << " "; node = node->next; } } // Driver code int main() { // Start with the empty list Node* head = NULL; /* Using push() to construct list 1->2->3->4->5 */ push(&head, 5); push(&head, 4); push(&head, 3); push(&head, 2); push(&head, 1); cout << "List before calling deleteAlt() "; printList(head); deleteAlt(head); cout << "List after calling deleteAlt() "; printList(head); return 0; } // This code is contributed by rathbhupendra |
Output:
List before calling deleteAlt() 1 2 3 4 5 List after calling deleteAlt() 1 3 5
Time Complexity: O(n) where n is the number of nodes in the given Linked List.
Auxiliary Space: O(1) because it is using constant space
Method 2 (Recursive):
Recursive code uses the same approach as method 1. The recursive code is simple and short but causes O(n) recursive function calls for a linked list of size n.
C++
/* Deletes alternate nodes of a list starting with head */void deleteAlt(Node *head) { if (head == NULL) return; Node *node = head->next; if (node == NULL) return; // Change the next link of head head->next = node->next; // Free memory allocated for node free(node); /* Recursively call for the new next of head */ deleteAlt(head->next); } // This code is contributed by rathbhupendra |
Time Complexity: O(n)
Auxiliary space: O(n) for call stack because using recursion
Please refer complete article on Delete alternate nodes of a Linked List for more details!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
