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:
// Java program to delete alternate nodes of a linked list
class LinkedList
{
Node head; // head of list
/* Linked list Node*/
class Node
{
int data;
Node next;
Node(int d) {data = d; next = null; }
}
void deleteAlt()
{
if (head == null)
return;
Node prev = head;
Node now = head.next;
while (prev != null && now != null)
{
/* Change next link of previus node */
prev.next = now.next;
/* Free node */
now = null;
/*Update prev and now */
prev = prev.next;
if (prev != null)
now = prev.next;
}
}
/* Utility functions */
/* Inserts a new Node at front of the list. */
public void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
/* Function to print linked list */
void printList()
{
Node temp = head;
while(temp != null)
{
System.out.print(temp.data+" ");
temp = temp.next;
}
System.out.println();
}
/* Drier program to test above functions */
public static void main(String args[])
{
LinkedList llist = new LinkedList();
/* Constructed Linked List is 1->2->3->4->5->null */
llist.push(5);
llist.push(4);
llist.push(3);
llist.push(2);
llist.push(1);
System.out.println("Linked List before calling deleteAlt() ");
llist.printList();
llist.deleteAlt();
System.out.println("Linked List after calling deleteAlt() ");
llist.printList();
}
}
/* This code is contributed by Rajat Mishra */
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:
/* 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)
