C Program To Delete Alternate Nodes Of A Linked List
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<stdio.h> #include<stdlib.h> // A linked list node struct Node { int data; struct Node *next; }; // Deletes alternate nodes of a list // starting with head void deleteAlt( struct Node *head) { if (head == NULL) return ; // Initialize prev and node to // be deleted struct Node *prev = head; struct Node *node = head->next; while (prev != NULL && node != NULL) { // Change next link of previous // node prev->next = node->next; // Free memory free (node); // 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( struct Node** head_ref, int new_data) { // Allocate node struct Node* new_node = ( struct Node*) malloc ( sizeof ( struct 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( struct Node *node) { while (node != NULL) { printf ( "%d " , node->data); node = node->next; } } // Driver code int main() { // Start with the empty list struct 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); printf ( "\nList before calling deleteAlt() \n" ); printList(head); deleteAlt(head); printf ( "\nList after calling deleteAlt() \n" ); printList(head); return 0; } |
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( struct Node *head) { if (head == NULL) return ; struct 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); } |
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!