#university exam

Question

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.

Answer 1

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

Comments

That link list is circular doubly linklist take contant time not circular linklist

Answer 2

@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

 

 

Answer 3

ans = O(Math.max(n1,n2))

Answer 4

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}