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.
In java programming, the solution is given below
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
Java Programming: Delete alternate nodes of linked list:
[pastacode lang=”java” manual=”%2F%2F%20Java%20program%20to%20delete%20alternate%20nodes%20of%20a%20linked%20list%0Aclass%20LinkedList%0A%7B%0A%20%20%20%20Node%20head%3B%20%20%2F%2F%20head%20of%20list%0A%20%20%0A%20%20%20%20%2F*%20Linked%20list%20Node*%2F%0A%20%20%20%20class%20Node%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20data%3B%0A%20%20%20%20%20%20%20%20Node%20next%3B%0A%20%20%20%20%20%20%20%20Node(int%20d)%20%7Bdata%20%3D%20d%3B%20next%20%3D%20null%3B%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20void%20deleteAlt()%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20if%20(head%20%3D%3D%20null)%20%0A%20%20%20%20%20%20%20%20%20%20return%3B%0A%20%0A%20%20%20%20%20%20%20Node%20prev%20%3D%20head%3B%0A%20%20%20%20%20%20%20Node%20now%20%3D%20head.next%3B%0A%20%0A%20%20%20%20%20%20%20while%20(prev%20!%3D%20null%20%26%26%20now%20!%3D%20null)%20%0A%20%20%20%20%20%20%20%7B%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%2F*%20Change%20next%20link%20of%20previus%20node%20*%2F%0A%20%20%20%20%20%20%20%20%20%20%20prev.next%20%3D%20now.next%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%2F*%20Free%20node%20*%2F%0A%20%20%20%20%20%20%20%20%20%20%20now%20%3D%20null%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%2F*Update%20prev%20and%20now%20*%2F%0A%20%20%20%20%20%20%20%20%20%20%20prev%20%3D%20prev.next%3B%0A%20%20%20%20%20%20%20%20%20%20%20if%20(prev%20!%3D%20null)%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20now%20%3D%20prev.next%3B%0A%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%2F*%20Utility%20functions%20*%2F%0A%20%0A%20%20%20%20%2F*%20Inserts%20a%20new%20Node%20at%20front%20of%20the%20list.%20*%2F%0A%20%20%20%20public%20void%20push(int%20new_data)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F*%201%20%26%202%3A%20Allocate%20the%20Node%20%26%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20Put%20in%20the%20data*%2F%0A%20%20%20%20%20%20%20%20Node%20new_node%20%3D%20new%20Node(new_data)%3B%0A%20%20%0A%20%20%20%20%20%20%20%20%2F*%203.%20Make%20next%20of%20new%20Node%20as%20head%20*%2F%0A%20%20%20%20%20%20%20%20new_node.next%20%3D%20head%3B%0A%20%20%0A%20%20%20%20%20%20%20%20%2F*%204.%20Move%20the%20head%20to%20point%20to%20new%20Node%20*%2F%0A%20%20%20%20%20%20%20%20head%20%3D%20new_node%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20Function%20to%20print%20linked%20list%20*%2F%0A%20%20%20%20void%20printList()%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20Node%20temp%20%3D%20head%3B%0A%20%20%20%20%20%20%20%20while(temp%20!%3D%20null)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20System.out.print(temp.data%2B%22%20%22)%3B%0A%20%20%20%20%20%20%20%20%20%20%20temp%20%3D%20temp.next%3B%0A%20%20%20%20%20%20%20%20%7D%20%20%0A%20%20%20%20%20%20%20%20System.out.println()%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%2F*%20Drier%20program%20to%20test%20above%20functions%20*%2F%0A%20%20%20%20public%20static%20void%20main(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20LinkedList%20llist%20%3D%20new%20LinkedList()%3B%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F*%20Constructed%20Linked%20List%20is%201-%3E2-%3E3-%3E4-%3E5-%3Enull%20*%2F%0A%20%20%20%20%20%20%20%20llist.push(5)%3B%0A%20%20%20%20%20%20%20%20llist.push(4)%3B%0A%20%20%20%20%20%20%20%20llist.push(3)%3B%0A%20%20%20%20%20%20%20%20llist.push(2)%3B%0A%20%20%20%20%20%20%20%20llist.push(1)%3B%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20System.out.println(%22Linked%20List%20before%20calling%20deleteAlt()%20%22)%3B%0A%20%20%20%20%20%20%20%20llist.printList()%3B%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20llist.deleteAlt()%3B%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20System.out.println(%22Linked%20List%20after%20calling%20deleteAlt()%20%22)%3B%0A%20%20%20%20%20%20%20%20llist.printList()%3B%0A%20%20%20%20%7D%0A%7D%20%0A%2F*%20This%20code%20is%20contributed%20by%20Rajat%20Mishra%20*%2F” 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 code is simple and short, but causes O(n) recursive function calls for a linked list of size n.
Java Programming:
[pastacode lang=”java” 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)