Python Program To Delete Alternate Nodes Of A Linked List
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!
Contact Us