InterviewSolution
Saved Bookmarks
InterviewSolution
| 1. |
Write a program to delete all odd positioned nodes from a circular linked list. (Consider 1-based indexing). |
|
Answer» The approach is to begin traversing the circular linked list by keeping track of the current node's POSITION USING a count VARIABLE. Delete the current node if it is at an odd position. Implementation: // l is the length of the linked listvoid DeleteAllOddNodes(struct Node** head_reference, int l){ int CNT = 0; struct Node *prev = *head_reference, *next = *head_reference; // check if the list is empty if (*head_reference == NULL) { cout<<"List is empty"<<endl; return; } // check if there is a single node in the list if (l == 1) { // Function to delete first node *head_reference=NULL; return; } while (l > 0) { // delete first position node as it is odd if (cnt == 0) { struct Node *t1 = *head_reference, *t2 = *head_reference; if (t1->next == t1) { *head_reference = NULL; } while(t1->next!=*head_reference) { t1 = t1->next; t2 = t1->next; } t1->next = t2->next; *head_reference = t1->next; free(t2); } // if the position is odd, delete that node if (cnt % 2 == 0 && cnt != 0) { struct Node* tmp = head_reference; if (head_reference == prev) { head_reference = prev->next; } while (tmp->next != prev) { tmp = tmp->next; } tmp->next = prev->next; free(prev); } prev = prev->next; next = prev->next; cnt++; l--; }turn; re}TIME Complexity: O(n^2) |
|