0 votes 0 votes Time complexity circular LL i think aswer is A . this Q is similar to https://gateoverflow.in/61880/complexity but here they haven't mentioned about any pointer. here is my explanation mehul vaidya asked Mar 11, 2018 mehul vaidya 573 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
2 votes 2 votes I did it this way. It will take constant amount of timr Ananya Jaiswal 1 answered Mar 12, 2018 Ananya Jaiswal 1 comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes if we insert a node in the middle of the list. then we have to traverse half of the list and it will take o(n) in best and worst case. if we insert node at the starting of the node then it will take constant time abhishekmehta4u answered Mar 11, 2018 abhishekmehta4u comment Share Follow See all 5 Comments See all 5 5 Comments reply mehul vaidya commented Mar 11, 2018 reply Follow Share But it is asking Time complexity to insert node at starting and not at middle 0 votes 0 votes Shubhanshu commented Mar 11, 2018 i edited by Shubhanshu Mar 11, 2018 reply Follow Share //Code to insert node at begining of the Circular singly Linked list void insert(node *head, int key) { node *temp = (node *)malloc(sizeof(node)); temp->next = NULL; temp->value = key; if(head == NULL) { head = temp; temp->next = temp; } else { node *q = head; while(q->next == head) // This loop take O(n) time q = q->next; q->next = temp; temp->next = head; head = temp; } return; } Option (D) is correct. 0 votes 0 votes abhishekmehta4u commented Mar 11, 2018 reply Follow Share @mehul vaidya you are right . for starting it will take o(1) –1 votes –1 votes mehul vaidya commented Mar 11, 2018 reply Follow Share I don't think this code is correct Observe this lines node *q = head; while(q->next = head) // This loop take O(n) time q = q->next; you are assigning head to q , then again you are traversing list to find q-> next = head. (it uses = instead of ==) after that you are doing temp->next = head; (that means pointer to start of Circular LL lost) instead of temp->next = head-> next ; 0 votes 0 votes mehul vaidya commented Mar 11, 2018 reply Follow Share thank you 0 votes 0 votes Please log in or register to add a comment.