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:

[pastacode lang=”c” manual=”%2F%2F%20C%20program%20to%20remove%20alternate%20nodes%20of%20a%20linked%20list%0A%23include%3Cstdio.h%3E%0A%23include%3Cstdlib.h%3E%0A%20%0A%2F*%20A%20linked%20list%20node%20*%2F%0Astruct%20node%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20struct%20node%20*next%3B%0A%7D%3B%0A%20%0A%2F*%20deletes%20alternate%20nodes%20of%20a%20list%20starting%20with%20head%20*%2F%0Avoid%20deleteAlt(struct%20node%20*head)%0A%7B%0A%20%20%20%20if%20(head%20%3D%3D%20NULL)%0A%20%20%20%20%20%20%20%20return%3B%0A%20%0A%20%20%20%20%2F*%20Initialize%20prev%20and%20node%20to%20be%20deleted%20*%2F%0A%20%20%20%20struct%20node%20*prev%20%3D%20head%3B%0A%20%20%20%20struct%20node%20*node%20%3D%20head-%3Enext%3B%0A%20%0A%20%20%20%20while%20(prev%20!%3D%20NULL%20%26%26%20node%20!%3D%20NULL)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F*%20Change%20next%20link%20of%20previous%20node%20*%2F%0A%20%20%20%20%20%20%20%20prev-%3Enext%20%3D%20node-%3Enext%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Free%20memory%20*%2F%0A%20%20%20%20%20%20%20%20free(node)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Update%20prev%20and%20node%20*%2F%0A%20%20%20%20%20%20%20%20prev%20%3D%20prev-%3Enext%3B%0A%20%20%20%20%20%20%20%20if%20(prev%20!%3D%20NULL)%0A%20%20%20%20%20%20%20%20%20%20%20%20node%20%3D%20prev-%3Enext%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F*%20UTILITY%20FUNCTIONS%20TO%20TEST%20fun1()%20and%20fun2()%20*%2F%0A%2F*%20Given%20a%20reference%20(pointer%20to%20pointer)%20to%20the%20head%0A%20%20of%20a%20list%20and%20an%20int%2C%20push%20a%20new%20node%20on%20the%20front%0A%20%20of%20the%20list.%20*%2F%0Avoid%20push(struct%20node**%20head_ref%2C%20int%20new_data)%0A%7B%0A%20%20%20%20%2F*%20allocate%20node%20*%2F%0A%20%20%20%20struct%20node*%20new_node%20%3D%0A%20%20%20%20%20%20%20%20(struct%20node*)%20malloc(sizeof(struct%20node))%3B%0A%20%0A%20%20%20%20%2F*%20put%20in%20the%20data%20%20*%2F%0A%20%20%20%20new_node-%3Edata%20%20%3D%20new_data%3B%0A%20%0A%20%20%20%20%2F*%20link%20the%20old%20list%20off%20the%20new%20node%20*%2F%0A%20%20%20%20new_node-%3Enext%20%3D%20(*head_ref)%3B%0A%20%0A%20%20%20%20%2F*%20move%20the%20head%20to%20point%20to%20the%20new%20node%20*%2F%0A%20%20%20%20(*head_ref)%20%20%20%20%3D%20new_node%3B%0A%7D%0A%20%0A%2F*%20Function%20to%20print%20nodes%20in%20a%20given%20linked%20list%20*%2F%0Avoid%20printList(struct%20node%20*node)%0A%7B%0A%20%20%20%20while%20(node%20!%3D%20NULL)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20printf(%22%25d%20%22%2C%20node-%3Edata)%3B%0A%20%20%20%20%20%20%20%20node%20%3D%20node-%3Enext%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F*%20Drier%20program%20to%20test%20above%20functions%20*%2F%0Aint%20main()%0A%7B%0A%20%20%20%20%2F*%20Start%20with%20the%20empty%20list%20*%2F%0A%20%20%20%20struct%20node*%20head%20%3D%20NULL%3B%0A%20%0A%20%20%20%20%2F*%20Using%20push()%20to%20construct%20below%20list%0A%20%20%20%20%20%201-%3E2-%3E3-%3E4-%3E5%20%20*%2F%0A%20%20%20%20push(%26head%2C%205)%3B%0A%20%20%20%20push(%26head%2C%204)%3B%0A%20%20%20%20push(%26head%2C%203)%3B%0A%20%20%20%20push(%26head%2C%202)%3B%0A%20%20%20%20push(%26head%2C%201)%3B%0A%20%0A%20%20%20%20printf(%22%5CnList%20before%20calling%20deleteAlt()%20%5Cn%22)%3B%0A%20%20%20%20printList(head)%3B%0A%20%0A%20%20%20%20deleteAlt(head)%3B%0A%20%0A%20%20%20%20printf(%22%5CnList%20after%20calling%20deleteAlt()%20%5Cn%22)%3B%0A%20%20%20%20printList(head)%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D%0A” message=”” highlight=”” provider=”manual”/]

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.

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:

[pastacode lang=”c” manual=”%2F*%20deletes%20alternate%20nodes%20of%20a%20list%20starting%20with%20head%20*%2F%0Avoid%20deleteAlt(struct%20node%20*head)%0A%7B%0A%20%20%20%20if%20(head%20%3D%3D%20NULL)%0A%20%20%20%20%20%20%20%20return%3B%0A%20%0A%20%20%20%20struct%20node%20*node%20%3D%20head-%3Enext%3B%0A%20%0A%20%20%20%20if%20(node%20%3D%3D%20NULL)%0A%20%20%20%20%20%20%20%20return%3B%0A%20%0A%20%20%20%20%2F*%20Change%20the%20next%20link%20of%20head%20*%2F%0A%20%20%20%20head-%3Enext%20%3D%20node-%3Enext%3B%0A%20%0A%20%20%20%20%2F*%20free%20memory%20allocated%20for%20node%20*%2F%0A%20%20%20%20free(node)%3B%0A%20%0A%20%20%20%20%2F*%20Recursively%20call%20for%20the%20new%20next%20of%20head%20*%2F%0A%20%20%20%20deleteAlt(head-%3Enext)%3B%0A%7D” message=”” highlight=”” provider=”manual”/]

Time Complexity: O(n)