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)

Categorized in:

Linked ListSingly Linked List

Tagged in:

, , , , , , , , , , , , , , , ,