{"id":27695,"date":"2018-04-09T20:22:50","date_gmt":"2018-04-09T14:52:50","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27695"},"modified":"2018-10-27T16:46:41","modified_gmt":"2018-10-27T11:16:41","slug":"java-algorithm-delete-alternate-nodes-linked-list","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-algorithm-delete-alternate-nodes-linked-list\/","title":{"rendered":"Delete alternate nodes of a Linked List"},"content":{"rendered":"

Given a Singly Linked List<\/a>, starting from the second node delete all alternate nodes of it.<\/p>\n

For example<\/strong>, if the given linked list is 1->2->3->4->5 then your function should convert it to 1->3->5, and<\/p>\n

if the given linked list<\/a> is 1->2->3->4 then convert it to 1->3.<\/span><\/p>\n

In java programming<\/a>, the solution is given below<\/p>\n

Method 1 (Iterative):<\/strong><\/span><\/h3>\n

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<\/p>\n

Java Programming: Delete alternate nodes of linked list:<\/strong><\/span><\/h4>\n
<\/div> 
\/\/ Java program to delete alternate nodes of a linked listclass 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 *\/<\/code><\/pre> <\/div>\n
Output:<\/strong><\/span><\/p>\n
List before calling deleteAlt() \r\n1 2 3 4 5 \r\nList after calling deleteAlt() \r\n1 3 5<\/pre>\n
Time Complexity:<\/strong><\/span> O(n) where n is the number of nodes in the given Linked List.<\/p>\n
Method 2 (Recursive):<\/strong><\/span><\/h3>\n
Recursive code uses the same approach as method 1. The recursive code is simple and short, but causes O(n)<\/strong> recursive function<\/a> calls for a linked list of size n.<\/p>\n
Java Programming:<\/span><\/strong><\/p>\n
 
 <\/div> 
\/* 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);}<\/code><\/pre> <\/div>\n
Time Complexity:<\/strong><\/span> O(n)<\/p>\n","protected":false},"excerpt":{"rendered":"
Java Algorithm – Delete alternate nodes of a Linked List – Linked List – Given a Singly Linked List, starting from the second node delete all alternate <\/p>\n","protected":false},"author":1,"featured_media":31261,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[79476,79478],"tags":[81988,81989,81962,81992,81961,81990,81933,81956,81957,81993,81963,81991,81995,81958,81994,81955,81959],"class_list":["post-27695","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-linked-list","category-singly-linked-list","tag-alternating-split-of-a-given-singly-linked-list","tag-delete-alternate-nodes-of-a-circular-linked-list","tag-delete-even-nodes-from-linked-list","tag-delete-even-nodes-from-linked-list-java","tag-delete-odd-nodes-linked-list","tag-delete-odd-nodes-linked-list-java","tag-even-odd-linked-list","tag-given-a-singly-linked-list","tag-group-all-odd-nodes-together-followed-by-the-even-nodes","tag-odd-even-linked-list-python","tag-rearrange-a-linked-list-such-that-all-even-and-odd-positioned-nodes-are-together","tag-remove-odd-numbers-from-linked-list","tag-segregate-even-and-odd-nodes-in-a-linked-list-c","tag-segregate-even-and-odd-nodes-in-a-linked-list-java","tag-segregate-even-and-odd-numbers-in-linked-list","tag-split-a-linked-list-into-even-and-odd-parts","tag-split-linked-list-into-two"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27695","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27695"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27695\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/31261"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27695"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27695"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27695"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}