Cpp Algorithm – Delete alternate nodes of a Linked List

Cpp Algorithm - Delete alternate nodes of a Linked List - Linked List - Given a Singly Linked List, starting from the second node delete all alternate

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 previous node and then free the memory allocated for the node

C++ Programming:

``````// 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 */
{
return;

/* Initialize prev and node to be deleted */

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 off the new node */

/* move the head to point to the 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;
}
}

/* Drier program to test above functions */
int main()
{

/* Using push() to construct below list
1->2->3->4->5  */

printf("\nList before calling deleteAlt() \n");

printf("\nList after calling deleteAlt() \n");

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.

READ  C Algorithm - Move last element to front of a given Linked List

Method 2 (Recursive)
Recursive code uses the same approach as method 1. The recursive coed is simple and short, but causes O(n) recursive function calls for a linked list of size n.

C++ Programming:

``````/* deletes alternate nodes of a list starting with head */
{
return;

if (node == NULL)
return;

/* free memory allocated for node */
free(node);

/* Recursively call for the new next of head */