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.
Python3
# Python3 program to remove alternate # nodes of a linked list import math # A linked list node class Node: def __init__(self, data): self.data = data self.next = None # Deletes alternate nodes # of a list starting with head def deleteAlt(head): if (head == None): return # Initialize prev and node to # be deleted prev = head now = head.next while (prev != None and now != None): # Change next link of previous # node prev.next = now.next # Free memory now = None # Update prev and node prev = prev.next if (prev != None): now = prev.next # UTILITY FUNCTIONS TO TEST # fun1() and fun2() # Given a reference (pointer to pointer) # to the head of a list and an , push a # new node on the front of the list. def push(head_ref, new_data): # Allocate node new_node = Node(new_data) # Put in the data new_node.data = new_data # Link the old list of the # new node new_node.next = head_ref # Move the head to point to the # new node head_ref = new_node return head_ref# Function to print nodes in a # given linked list def printList(node): while (node != None): print(node.data, end = " ") node = node.next # Driver code if __name__=='__main__': # Start with the empty list head = None # Using head=push() to construct # list 1.2.3.4.5 head = push(head, 5) head = push(head, 4) head = push(head, 3) head = push(head, 2) head = push(head, 1) print("List before calling deleteAlt() ") printList(head) deleteAlt(head) print("List after calling deleteAlt() ") printList(head) # This code is contributed by Srathore |
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.
Python3
# Deletes alternate nodes of a list # starting with head def deleteAlt(head): if (head == None): return node = head.next if (node == None): 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) # This code is contributed by Srathore |
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!
You’ll access excellent video content by our CEO, Sandeep Jain, tackle common interview questions, and engage in real-time coding contests covering various DSA topics. We’re here to prepare you thoroughly for online assessments and interviews.
Ready to dive in? Explore our free demo content and join our DSA course, trusted by over 100,000neveropen! Whether it’s DSA in C++, Java, Python, or JavaScript we’ve got you covered. Let’s embark on this exciting journey together!
