GATE Overflow Test Series | Data Structures | Test 1 | Question: 11

Question

Let $L$ be a linked list of $n$ elements and $I$ be another linked list of $k$ node positions in $L$ ($n/4 < k < n/2)$ and elements in $I$ are not necessarily in sorted order. The best possible algorithm (use $O(1)$ extra space if required and assuming only comparison based sorting) to print the values in $L$ as per the node positions in $I$ will run in _____

• A. $\Theta(n)$
• B. $\Theta (n \log n)$
• C. $\Theta (n .k \log k) $
• D. $\Theta (nk)$

Comments

@gatecse Could you explain the last two lines of the question.

What is meant by “print values in L as per node positions in I” ??

---

The question is slightly misinterpreted by many. As much as I can interpret, the question is trying to say that –

We have a linked list L which have N nodes which contains some random values (We will not care about it).

We have another linked list I of K nodes which contains some integers which denotes index or positions of some [n/4 < k <n/2] nodes of linked list L. It may or may not be sorted.

For e.g.

L = ‘d’ → ‘a’ → ‘b’ → ‘o’ → ‘c’ → ‘z’  [L containing some alphabets.]

I = 3 → 5 → 1

According to the question, now we need to print the values of 3rd, 5th and 1st position of the linked list L, in any order.

We can sort I in O(KlogK) time.

I = 1 → 3 → 5.

Then, we can just do a simple traversal of the linked list L and get the values in O(N) time.

Total Complexity = O(KlogK) + O(N) = O(NlogN) [ As K is asymptotically similar to N ].

---

@DebSujit Your interpretation is correct. What part of the question text is not aligning with it?

---

“I be another linked list of K node positions” to “I be another linked list of K nodes containing positions of L.”

“print values in L as per node positions in I” to “print values of L as per the positions given in I”

will make it more interpretable.

Answer 1

The best algorithm here will do sorting of the linked list $I$ which can be done in $\Theta(k \log k)$ time and then one can simply do a traversal of $L$ in $\Theta(n).$ So, total complexity is $\Theta(k \log k) + \Theta(n).$

Since, $n/4 < k < n/2,$ we get $ k = \Theta(n).$

So, $\Theta(k \log k) + \Theta(n) \implies \Theta(n \log n) + \Theta(n) = \Theta(n \log n).$

Comments

@gatecse @Arjun

Sir, maybe I’m missing something. Which algorithms sorts a LL in nlogn TC with O(1) space? Here k is in order of n so how it is possible to sort LL I (of size k) in nlogn time with O(1) Space? 

---

Does this help?

https://stackoverflow.com/questions/1525117/whats-the-fastest-algorithm-for-sorting-a-linked-list

---

Thanks for sharing sir. I was confused why space was O(1). It got cleared after looking at the implementation.