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.
Method 1 (Iterative):
Keep track of previous of the node to be deleted. First, change the next link of the previous node and iteratively move to the next node.
Java
// Java program to delete alternate // nodes of a linked listclass LinkedList{ // Head of list Node head; // 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 previous 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(); } // Driver code 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.
Auxiliary Space: O(1) because it is using constant space
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
/* Deletes alternate nodes of a list starting with head */static Node deleteAlt(Node head) { if (head == null) return; Node node = head.next; if (node == null) return; // Change the next link of head head.next = node.next; /* Recursively call for the new next of head */ head.next = deleteAlt(head.next); } // This code is contributed by Arnab Kundu |
Time Complexity: O(n)
Auxiliary space: O(n) for call stack because using recursion
Please refer complete article on Delete alternate nodes of a Linked List for more details!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
