Delete all odd or even position nodes from circular linked list
Given a Singly Circular Linked List, starting from the first node delete all odd position nodes in it.
Note: Linked list is considered to have 1-based indexing. That is, first element in the linked list is at position 1.
Examples:
Input : List = 99->11->22->33 Output : 11->33 Input : List = 90->10->20->30 Output : 10->30
The idea is to start traversing the circular linked list using a count variable to keep track of the position of current node. If the current node is at odd position then delete that node using the approach discussed in Delete node from Circular Linked List.
Implementation: Function to delete all odd positioned nodes.
C++
// Function to delete that all// node whose index position is oddvoid DeleteAllOddNode(struct Node** head){ int len = Length(*head); int count = 0; struct Node *previous = *head, *next = *head; // check list have any node // if not then return if (*head == NULL) { printf("\nDelete Last List is empty\n"); return; } // if list have single node means // odd position then delete it if (len == 1) { DeleteFirst(head); return; } // traverse first to last if // list have more than one node while (len > 0) { // delete first position node // which is odd position if (count == 0) { // Function to delete first node DeleteFirst(head); } // check position is odd or not // if yes then delete node if (count % 2 == 0 && count != 0) { deleteNode(*head, previous); } previous = previous->next; next = previous->next; len--; count++; } return;} |
Java
// Function to delete that all// node whose index position is oddstatic void DeleteAllOddNode(Node head){ int len = Length(head); int count = 0; Node previous = head, next = head; // Check list have any node // if not then return if (head == null) { System.out.printf("\nDelete Last List is empty\n"); return; } // If list have single node means // odd position then delete it if (len == 1) { DeleteFirst(head); return; } // Traverse first to last if // list have more than one node while (len > 0) { // Delete first position node // which is odd position if (count == 0) { // Function to delete first node DeleteFirst(head); } // Check position is odd or not // if yes then delete node if (count % 2 == 0 && count != 0) { deleteNode(head, previous); } previous = previous.next; next = previous.next; len--; count++; } return;}// This code is contributed by aashish1995 |
C#
// Function to delete that all// node whose index position is oddstatic Node DeleteAllOddNode(Node head){ int len = Length(head); int count = 0; Node previous = head, next = head; // check list have any node // if not then return if (head == null) { Console.Write("\nDelete Last List is empty\n"); return null; } // if list have single node means // odd position then delete it if (len == 1) { head = DeleteFirst(head); return head; } // traverse first to last if // list have more than one node while (len > 0) { // delete first position node // which is odd position if (count == 0) { // Function to delete first node head = DeleteFirst(head); } // check position is odd or not // if yes then delete node // Note: Considered 1 based indexing if (count % 2 == 0 && count != 0) { head = deleteNode(head, previous); } previous = previous.next; next = previous.next; len--; count++; } return head;}// This code is contributed by shivanisinghss2110 |
Javascript
<script>// Function to delete that all// node whose index position is oddfunction DeleteAllOddNode( head){ let len = Length(head); let count = 0; var previous = head, next = head; // Check list have any node // if not then return if (head == null) { document.write("</br>" + "Delete Last List is empty" + "</br>"); return null; } // If list have single node means // odd position then delete it if (len == 1) { head = DeleteFirst(head); return head; } // Traverse first to last if // list have more than one node while (len > 0) { // Delete first position node // which is odd position if (count == 0) { // Function to delete first node head = DeleteFirst(head); } // Check position is odd or not // if yes then delete node // Note: Considered 1 based indexing if (count % 2 == 0 && count != 0) { head = deleteNode(head, previous); } previous = previous.next; next = previous.next; len--; count++; } return head;}// This code is contributed by itsok</script> |
Python3
# Function to delete odd position nodesdef DeleteAllOddNode(head): len = Length(head) count = 0 previous = head next = head # check list have any node # if not then return if (head == None): print("\nDelete Last List is empty") return # if list have single node means # odd position then delete it if (len == 1): head=DeleteFirst(head) return head # traverse first to last if # list have more than one node while (len > 0): # delete first position node # which is odd position if (count == 0): # Function to delete first node head=DeleteFirst(head) # check position is odd or not # if yes then delete node # Note: Considered 1 based indexing if (count % 2 == 0 and count != 0): deleteNode(head, previous) previous = previous.next next = previous.next len-=1 count+=1 return head |
Delete all even position nodes from circular linked list
Given a Singly Circular Linked List. The task is to delete all nodes at even positions in this list. That is all starting from the second node delete all alternate nodes of the list.
Examples:
Input : List = 99->11->22->33 Output : 99->22 Input : List = 90->10->20->30 Output : 90->20
Note: Linked list is considered to have 1-based indexing. That is, first element in the linked list is at position 1.
The idea is to start traversing the circular linked list using a count variable to keep track of the position of the current node. If the current node is at even position then delete that node using the approach discussed in Delete node from Circular Linked List.
Implementation: Function to delete even positioned nodes.
C++
// Function to delete all even position nodesvoid DeleteAllEvenNode(struct Node** head){ // Take size of list int len = Length(*head); int count = 1; struct Node *previous = *head, *next = *head; // Check list is empty // if empty simply return if (*head == NULL) { printf("\nList is empty\n"); return; } // if list have single node // then return if (len < 2) { return; } // make first node is previous previous = *head; // make second node is current next = previous->next; while (len > 0) { // check node number is even // if node is even then // delete that node if (count % 2 == 0) { previous->next = next->next; free(next); previous = next->next; next = previous->next; } len--; count++; } return;} |
Java
// Function to delete all even position nodesstatic Node DeleteAllEvenNode( Node head){ // Take size of list int len = Length(head); int count = 1; Node previous = head, next = head; // Check list is empty // if empty simply return if (head == null) { System.out.printf("\nList is empty\n"); return null; } // if list have single node // then return if (len < 2) { return null; } // make first node is previous previous = head; // make second node is current next = previous.next; while (len > 0) { // check node number is even // if node is even then // delete that node if (count % 2 == 0) { previous.next = next.next; previous = next.next; next = previous.next; } len--; count++; } return head;}// This code is contributed by rutvik_56 |
C#
// Function to delete all even position nodesstatic Node DeleteAllEvenNode(Node head){ // Take size of list int len = Length(head); int count = 1; Node previous = head, next = head; // Check list is empty // if empty simply return if (head == null) { Console.Write("\nList is empty\n"); return null; } // If list have single node // then return if (len < 2) { return null; } // Make first node is previous previous = head; // Make second node is current next = previous.next; while (len > 0) { // Check node number is even // if node is even then // delete that node if (count % 2 == 0) { previous.next = next.next; previous = next.next; next = previous.next; } len--; count++; } return head;}// This code is contributed by pratham76 |
Javascript
<script>// Function to delete all even position nodesfunction DeleteAllEvenNode( head){ // Take size of list var len = Length(head); var count = 1; var previous = head, next = head; // Check list is empty // if empty simply return if (head == null) { document.write("\nList is empty\n"); return null; } // if list have single node // then return if (len < 2) { return null; } // make first node is previous previous = head; // make second node is current next = previous.next; while (len > 0) { // check node number is even // if node is even then // delete that node if (count % 2 == 0) { previous.next = next.next; previous = next.next; next = previous.next; } len--; count++; } return head;}// This code contributed by umadevi9616</script> |
Python3
# Function to delete all even position nodesdef DeleteAllEvenNode(head): # Take size of list len = Length(head) count = 1 previous = head next = head # Check list is empty # if empty simply return if (head == None): print("\nList is empty") return # if list have single node # then return if (len < 2): return # make first node is previous previous = head # make second node is current next = previous.next while (len > 0): # check node number is even # if node is even then # delete that node if (count % 2 == 0): previous.next = next.next # del(next) previous = next.next next = previous.next len-=1 count+=1 return head |
Implementation: Program to delete Even or Odd positioned nodes.
C++
// C++ program to delete all even and odd position// nodes from Singly Circular Linked list#include <bits/stdc++.h>// structure for a nodestruct Node { int data; struct Node* next;};// Function return number of nodes present in listint Length(struct Node* head){ struct Node* current = head; int count = 0; // if list is empty simply return length zero if (head == NULL) { return 0; } // traverse first to last node else { do { current = current->next; count++; } while (current != head); } return count;}// Function print data of listvoid Display(struct Node* head){ struct Node* current = head; // if list is empty simply show message if (head == NULL) { printf("\nDisplay List is empty\n"); return; } // traverse first to last node else { do { printf("%d ", current->data); current = current->next; } while (current != head); }}/* Function to insert a node at the end of a Circular linked list */void Insert(struct Node** head, int data){ struct Node* current = *head; // Create a new node struct Node* newNode = new Node; // check node is created or not if (!newNode) { printf("\nMemory Error\n"); return; } // insert data into newly created node newNode->data = data; // check list is empty // if not have any node then // make first node it if (*head == NULL) { newNode->next = newNode; *head = newNode; return; } // if list have already some node else { // move first node to last node while (current->next != *head) { current = current->next; } // put first or head node address in new node link newNode->next = *head; // put new node address into last node link(next) current->next = newNode; }}// Utility function to delete a Nodevoid deleteNode(struct Node* head_ref, struct Node* del){ struct Node* temp = head_ref; // If node to be deleted is head node if (head_ref == del) { head_ref = del->next; } // traverse list till not found // delete node while (temp->next != del) { temp = temp->next; } // copy address of node temp->next = del->next; // Finally, free the memory // occupied by del free(del); return;}// Function to delete First node of// Circular Linked Listvoid DeleteFirst(struct Node** head){ struct Node *previous = *head, *next = *head; // check list have any node // if not then return if (*head == NULL) { printf("\nList is empty\n"); return; } // check list have single node // if yes then delete it and return if (previous->next == previous) { *head = NULL; return; } // traverse second to first while (previous->next != *head) { previous = previous->next; next = previous->next; } // now previous is last node and // next is first node of list // first node(next) link address // put in last node(previous) link previous->next = next->next; // make second node as head node *head = previous->next; free(next); return;}// Function to delete odd position nodesvoid DeleteAllOddNode(struct Node** head){ int len = Length(*head); int count = 0; struct Node *previous = *head, *next = *head; // check list have any node // if not then return if (*head == NULL) { printf("\nDelete Last List is empty\n"); return; } // if list have single node means // odd position then delete it if (len == 1) { DeleteFirst(head); return; } // traverse first to last if // list have more than one node while (len > 0) { // delete first position node // which is odd position if (count == 0) { // Function to delete first node DeleteFirst(head); } // check position is odd or not // if yes then delete node // Note: Considered 1 based indexing if (count % 2 == 0 && count != 0) { deleteNode(*head, previous); } previous = previous->next; next = previous->next; len--; count++; } return;}// Function to delete all even position nodesvoid DeleteAllEvenNode(struct Node** head){ // Take size of list int len = Length(*head); int count = 1; struct Node *previous = *head, *next = *head; // Check list is empty // if empty simply return if (*head == NULL) { printf("\nList is empty\n"); return; } // if list have single node // then return if (len < 2) { return; } // make first node is previous previous = *head; // make second node is current next = previous->next; while (len > 0) { // check node number is even // if node is even then // delete that node if (count % 2 == 0) { previous->next = next->next; free(next); previous = next->next; next = previous->next; } len--; count++; } return;}// Driver Codeint main(){ struct Node* head = NULL; Insert(&head, 99); Insert(&head, 11); Insert(&head, 22); Insert(&head, 33); Insert(&head, 44); Insert(&head, 55); Insert(&head, 66); // Deleting Odd positioned nodes printf("Initial List: "); Display(head); printf("\nAfter deleting Odd position nodes: "); DeleteAllOddNode(&head); Display(head); // Deleting Even positioned nodes printf("\n\nInitial List: "); Display(head); printf("\nAfter deleting even position nodes: "); DeleteAllEvenNode(&head); Display(head); return 0;} |
Java
// Java program to delete all even and odd position// nodes from Singly Circular Linked listclass GFG{ // structure for a nodestatic class Node{ int data; Node next;};// Function return number of nodes present in liststatic int Length(Node head){ Node current = head; int count = 0; // if list is empty simply return length zero if (head == null) { return 0; } // traverse first to last node else { do { current = current.next; count++; } while (current != head); } return count;}// Function print data of liststatic void Display( Node head){ Node current = head; // if list is empty simply show message if (head == null) { System.out.printf("\nDisplay List is empty\n"); return; } // traverse first to last node else { do { System.out.printf("%d ", current.data); current = current.next; } while (current != head); }}/* Function to insert a node at the end of a Circular linked list */static Node Insert(Node head, int data){ Node current = head; // Create a new node Node newNode = new Node(); // check node is created or not if (newNode == null) { System.out.printf("\nMemory Error\n"); return null; } // insert data into newly created node newNode.data = data; // check list is empty // if not have any node then // make first node it if (head == null) { newNode.next = newNode; head = newNode; return head; } // if list have already some node else { // move first node to last node while (current.next != head) { current = current.next; } // put first or head node address in new node link newNode.next = head; // put new node address into last node link(next) current.next = newNode; } return head;}// Utility function to delete a Nodestatic Node deleteNode(Node head_ref, Node del){ Node temp = head_ref; // If node to be deleted is head node if (head_ref == del) { head_ref = del.next; } // traverse list till not found // delete node while (temp.next != del) { temp = temp.next; } // copy address of node temp.next = del.next; return head_ref;}// Function to delete First node of// Circular Linked Liststatic Node DeleteFirst(Node head){ Node previous = head, next = head; // check list have any node // if not then return if (head == null) { System.out.printf("\nList is empty\n"); return head; } // check list have single node // if yes then delete it and return if (previous.next == previous) { head = null; return head; } // traverse second to first while (previous.next != head) { previous = previous.next; next = previous.next; } // now previous is last node and // next is first node of list // first node(next) link address // put in last node(previous) link previous.next = next.next; // make second node as head node head = previous.next; return head;}// Function to delete odd position nodesstatic Node DeleteAllOddNode(Node head){ int len = Length(head); int count = 0; Node previous = head, next = head; // check list have any node // if not then return if (head == null) { System.out.printf("\nDelete Last List is empty\n"); return null; } // if list have single node means // odd position then delete it if (len == 1) { head = DeleteFirst(head); return head; } // traverse first to last if // list have more than one node while (len > 0) { // delete first position node // which is odd position if (count == 0) { // Function to delete first node head = DeleteFirst(head); } // check position is odd or not // if yes then delete node // Note: Considered 1 based indexing if (count % 2 == 0 && count != 0) { head = deleteNode(head, previous); } previous = previous.next; next = previous.next; len--; count++; } return head;}// Function to delete all even position nodesstatic Node DeleteAllEvenNode( Node head){ // Take size of list int len = Length(head); int count = 1; Node previous = head, next = head; // Check list is empty // if empty simply return if (head == null) { System.out.printf("\nList is empty\n"); return null; } // if list have single node // then return if (len < 2) { return null; } // make first node is previous previous = head; // make second node is current next = previous.next; while (len > 0) { // check node number is even // if node is even then // delete that node if (count % 2 == 0) { previous.next = next.next; previous = next.next; next = previous.next; } len--; count++; } return head;}// Driver Codepublic static void main(String args[]){ Node head = null; head = Insert(head, 99); head = Insert(head, 11); head = Insert(head, 22); head = Insert(head, 33); head = Insert(head, 44); head = Insert(head, 55); head = Insert(head, 66); // Deleting Odd positioned nodes System.out.printf("Initial List: "); Display(head); System.out.printf("\nAfter deleting Odd position nodes: "); head = DeleteAllOddNode(head); Display(head); // Deleting Even positioned nodes System.out.printf("\n\nInitial List: "); Display(head); System.out.printf("\nAfter deleting even position nodes: "); head = DeleteAllEvenNode(head); Display(head);}}// This code is contributed by Arnab Kundu |
C#
// C# program to delete all even and // odd position nodes from // Singly Circular Linked listusing System; class GFG{ // structure for a nodeclass Node{ public int data; public Node next;};// Function return number of nodes// present in liststatic int Length(Node head){ Node current = head; int count = 0; // if list is empty simply return // length zero if (head == null) { return 0; } // traverse first to last node else { do { current = current.next; count++; } while (current != head); } return count;}// Function print data of liststatic void Display( Node head){ Node current = head; // if list is empty simply show message if (head == null) { Console.Write("\nDisplay List is empty\n"); return; } // traverse first to last node else { do { Console.Write("{0} ", current.data); current = current.next; } while (current != head); }}/* Function to insert a node at the end of a Circular linked list */static Node Insert(Node head, int data){ Node current = head; // Create a new node Node newNode = new Node(); // check node is created or not if (newNode == null) { Console.Write("\nMemory Error\n"); return null; } // insert data into newly created node newNode.data = data; // check list is empty // if not have any node then // make first node it if (head == null) { newNode.next = newNode; head = newNode; return head; } // if list have already some node else { // move first node to last node while (current.next != head) { current = current.next; } // put first or head node address // in new node link newNode.next = head; // put new node address into // last node link(next) current.next = newNode; } return head;}// Utility function to delete a Nodestatic Node deleteNode(Node head_ref, Node del){ Node temp = head_ref; // If node to be deleted is head node if (head_ref == del) { head_ref = del.next; } // traverse list till not found // delete node while (temp.next != del) { temp = temp.next; } // copy address of node temp.next = del.next; return head_ref;}// Function to delete First node of// Circular Linked Liststatic Node DeleteFirst(Node head){ Node previous = head, next = head; // check list have any node // if not then return if (head == null) { Console.Write("\nList is empty\n"); return head; } // check list have single node // if yes then delete it and return if (previous.next == previous) { head = null; return head; } // traverse second to first while (previous.next != head) { previous = previous.next; next = previous.next; } // now previous is last node and // next is first node of list // first node(next) link address // put in last node(previous) link previous.next = next.next; // make second node as head node head = previous.next; return head;}// Function to delete odd position nodesstatic Node DeleteAllOddNode(Node head){ int len = Length(head); int count = 0; Node previous = head, next = head; // check list have any node // if not then return if (head == null) { Console.Write("\nDelete Last List is empty\n"); return null; } // if list have single node means // odd position then delete it if (len == 1) { head = DeleteFirst(head); return head; } // traverse first to last if // list have more than one node while (len > 0) { // delete first position node // which is odd position if (count == 0) { // Function to delete first node head = DeleteFirst(head); } // check position is odd or not // if yes then delete node // Note: Considered 1 based indexing if (count % 2 == 0 && count != 0) { head = deleteNode(head, previous); } previous = previous.next; next = previous.next; len--; count++; } return head;}// Function to delete all even position nodesstatic Node DeleteAllEvenNode( Node head){ // Take size of list int len = Length(head); int count = 1; Node previous = head, next = head; // Check list is empty // if empty simply return if (head == null) { Console.Write("\nList is empty\n"); return null; } // if list have single node // then return if (len < 2) { return null; } // make first node is previous previous = head; // make second node is current next = previous.next; while (len > 0) { // check node number is even // if node is even then // delete that node if (count % 2 == 0) { previous.next = next.next; previous = next.next; next = previous.next; } len--; count++; } return head;}// Driver Codepublic static void Main(String []args){ Node head = null; head = Insert(head, 99); head = Insert(head, 11); head = Insert(head, 22); head = Insert(head, 33); head = Insert(head, 44); head = Insert(head, 55); head = Insert(head, 66); // Deleting Odd positioned nodes Console.Write("Initial List: "); Display(head); Console.Write("\nAfter deleting Odd position nodes: "); head = DeleteAllOddNode(head); Display(head); // Deleting Even positioned nodes Console.Write("\n\nInitial List: "); Display(head); Console.Write("\nAfter deleting even position nodes: "); head = DeleteAllEvenNode(head); Display(head);}}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript program to delete all even and odd position// nodes from Singly Circular Linked list// Link list nodeclass Node { constructor() { this.data = 0; this.next = null; } } // Function return number of nodes present in listfunction Length( head){ var current = head; let count = 0; // if list is empty simply return length zero if (head == null) { return 0; } // traverse first to last node else { do { current = current.next; count++; } while (current != head); } return count;}// Function print data of listfunction Display( head){ var current = head; // if list is empty simply show message if (head == null) { document.write("</br>"+"Display List is empty"+"</br>"); return; } // traverse first to last node else { do { document.write( current.data + " "); current = current.next; } while (current != head); }}/* Function to insert a node at the end ofa Circular linked list */function Insert( head, data){ var current = head; // Create a new node var newNode = new Node(); // check node is created or not if (newNode == null) { document.write("</br>"+"Memory Error"+"</br>"); return null; } // insert data into newly created node newNode.data = data; // check list is empty // if not have any node then // make first node it if (head == null) { newNode.next = newNode; head = newNode; return head; } // if list have already some node else { // move first node to last node while (current.next != head) { current = current.next; } // put first or head node address in new node link newNode.next = head; // put new node address into last node link(next) current.next = newNode; } return head;}// Utility function to delete a Nodefunction deleteNode( head_ref, del){ var temp = head_ref; // If node to be deleted is head node if (head_ref == del) { head_ref = del.next; } // traverse list till not found // delete node while (temp.next != del) { temp = temp.next; } // copy address of node temp.next = del.next; return head_ref;}// Function to delete First node of// Circular Linked Listfunction DeleteFirst( head){ var previous = head, next = head; // check list have any node // if not then return if (head == null) { document.write("</br>"+"List is empty"+"</br>"); return head; } // check list have single node // if yes then delete it and return if (previous.next == previous) { head = null; return head; } // traverse second to first while (previous.next != head) { previous = previous.next; next = previous.next; } // now previous is last node and // next is first node of list // first node(next) link address // put in last node(previous) link previous.next = next.next; // make second node as head node head = previous.next; return head;}// Function to delete odd position nodesfunction DeleteAllOddNode( head){ let len = Length(head); let count = 0; var previous = head, next = head; // check list have any node // if not then return if (head == null) { document.write("</br>"+"Delete Last List is empty"+"</br>"); return null; } // if list have single node means // odd position then delete it if (len == 1) { head = DeleteFirst(head); return head; } // traverse first to last if // list have more than one node while (len > 0) { // delete first position node // which is odd position if (count == 0) { // Function to delete first node head = DeleteFirst(head); } // check position is odd or not // if yes then delete node // Note: Considered 1 based indexing if (count % 2 == 0 && count != 0) { head = deleteNode(head, previous); } previous = previous.next; next = previous.next; len--; count++; } return head;}// Function to delete all even position nodesfunction DeleteAllEvenNode( head){ // Take size of list let len = Length(head); let count = 1; var previous = head, next = head; // Check list is empty // if empty simply return if (head == null) { document.write("</br>"+"List is empty"+"</br>"); return null; } // if list have single node // then return if (len < 2) { return null; } // make first node is previous previous = head; // make second node is current next = previous.next; while (len > 0) { // check node number is even // if node is even then // delete that node if (count % 2 == 0) { previous.next = next.next; previous = next.next; next = previous.next; } len--; count++; } return head;}// Driver Codevar head = null;head = Insert(head, 99);head = Insert(head, 11);head = Insert(head, 22);head = Insert(head, 33);head = Insert(head, 44);head = Insert(head, 55);head = Insert(head, 66);// Deleting Odd positioned nodesdocument.write("Initial List: ");Display(head);document.write("</br>"+"After deleting Odd position nodes: ");head = DeleteAllOddNode(head);Display(head);// Deleting Even positioned nodesdocument.write("</br>"+"</br>"+"Initial List: ");Display(head);document.write("</br>"+"After deleting even position nodes: ");head = DeleteAllEvenNode(head);Display(head); // This code is contributed by jana_sayanta.</script> |
Python3
# Python3 program to delete all even and odd position# nodes from Singly Circular Linked list# class for a nodeclass Node: def __init__(self,data): self.data=data self.next=None# Function return number of nodes present in listdef Length(head): current = head count = 0 # if list is empty simply return length zero if head == None: return 0 # traverse first to last node else: while(True): current = current.next count+=1 if current == head: break return count# Function print data of listdef Display(head): current = head # if list is empty simply show message if head == None: print("\nDisplay List is empty") return # traverse first to last node else: while True: print(current.data,end=' ') current = current.next if current == head: break# Function to insert a node at the end of # a Circular linked listdef Insert(head, data): current = head # Create a new node newNode = Node(data) # check list is empty # if not have any node then # make first node it if head == None: newNode.next = newNode head = newNode return # if list have already some node else: # move first node to last node while (current.next != head): current = current.next # put first or head node address in new node link newNode.next = head # put new node address into last node link(next) current.next = newNode # Utility function to delete a Nodedef deleteNode(head_ref, del_ref): temp = head_ref # If node to be deleted is head node if (head_ref == del_ref): head_ref = del_ref.next # traverse list till not found # delete node while (temp.next != del_ref): temp = temp.next # copy address of node temp.next = del_ref.next # Finally, free the memory # occupied by del del(del_ref) return# Function to delete First node of# Circular Linked Listdef DeleteFirst(head): previous = head; next = head # check list have any node # if not then return if (head == None): print("\nList is empty") return # check list have single node # if yes then delete it and return if (previous.next == previous): return None # traverse second to first while (previous.next != head): previous = previous.next next = previous.next # now previous is last node and # next is first node of list # first node(next) link address # put in last node(previous) link previous.next = next.next # make second node as head node head = previous.next return head# Function to delete odd position nodesdef DeleteAllOddNode(head): len = Length(head) count = 0 previous = head next = head # check list have any node # if not then return if (head == None): print("\nDelete Last List is empty") return # if list have single node means # odd position then delete it if (len == 1): head=DeleteFirst(head) return head # traverse first to last if # list have more than one node while (len > 0): # delete first position node # which is odd position if (count == 0): # Function to delete first node head=DeleteFirst(head) # check position is odd or not # if yes then delete node # Note: Considered 1 based indexing if (count % 2 == 0 and count != 0): deleteNode(head, previous) previous = previous.next next = previous.next len-=1 count+=1 return head# Function to delete all even position nodesdef DeleteAllEvenNode(head): # Take size of list len = Length(head) count = 1 previous = head next = head # Check list is empty # if empty simply return if (head == None): print("\nList is empty") return # if list have single node # then return if (len < 2): return # make first node is previous previous = head # make second node is current next = previous.next while (len > 0): # check node number is even # if node is even then # delete that node if (count % 2 == 0): previous.next = next.next # del(next) previous = next.next next = previous.next len-=1 count+=1 return# Driver Codeif __name__ == '__main__': head = Node(99) head.next=head Insert(head, 11) Insert(head, 22) Insert(head, 33) Insert(head, 44) Insert(head, 55) Insert(head, 66) # Deleting Odd positioned nodes print("Initial List: ",end='') Display(head) print("\nAfter deleting Odd position nodes: ",end='') head=DeleteAllOddNode(head) Display(head) # Deleting Even positioned nodes print("\n\nInitial List: ",end='') Display(head) print("\nAfter deleting even position nodes: ",end='') DeleteAllEvenNode(head) Display(head) print()# This code is contributed by Amartya Ghosh |
Output
Initial List: 99 11 22 33 44 55 66 After deleting Odd position nodes: 11 33 55 Initial List: 11 33 55 After deleting even position nodes: 11 55
Complexity Analysis:
- Time Complexity: O(N)
- Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
