0 votes 0 votes What will be the complexity of merging two circular single linked list? You can consider the sizes of the linked lists are n1 and n2, respectively. DS linked-list + – amit166 asked Jan 9, 2022 • edited Jun 15, 2022 by Arjun amit166 529 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes I think answer should be O(1), because we just have to merge linked list and not having any constraint of maintain sorting. For more details refer this website- data structures - Linked List Concatenation In O(1) Time - Stack Overflow amitraj123 answered Jan 9, 2022 amitraj123 comment Share Follow See 1 comment See all 1 1 comment reply amit166 commented Jan 10, 2022 reply Follow Share That link list is circular doubly linklist take contant time not circular linklist 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes @amit166 The time complexity of this method will be O(m * n) where m and n are the numbers of nodes in two lists.... You can't do it with an array implementation, because you end up having to allocate more memory and copy the new resulting list to it... Even if the array already has memory allocated, you still have to copy all of the new items to it... So it's either O(m+n) or O(n) (where m and n are the lengths of the individual lists, respectively)… 1. https://gateoverflow.in/2220/Gate-cse-1997-question-1-4 2. https://gateoverflow.in/217564/Gate-cs-mock-2018 3. https://gateoverflow.in/13746/Does-concatenation-circular-linked-lists-takes-constant-time aaa 1 answered Jan 10, 2022 aaa 1 comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes ans = O(Math.max(n1,n2)) Hania3006 answered Jan 29, 2022 Hania3006 comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes In case of simple linked list, complexity of merging takes : O(n1+n2) {We need to find both list tail by using The Tortoise and the Hare (Floyd’s Algorithm)} while in case of Doubly linked list : O(1) {Change of few pointers} Udhay Brahmi answered Feb 8, 2022 Udhay Brahmi comment Share Follow See all 0 reply Please log in or register to add a comment.