# Delete alternate nodes of a Linked List

Java 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.

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
{

/* 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 */

/* 4. Move the head to point to 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[])
{

/* 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 */

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

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