Hi,
I am studying algorithms and how efficient they can be. So I have a question concerning merging of linked lists.
If I have two linked lists. One is double the size of the other. And and larger one is sorted, where as the smaller one is unsorted. Is there a way to take the elements from the small unsorted linked list and add it to the larger sorted list, so that the new list remains sorted, without reaching O(n^2) ??
If so, how would you carryout this operation?
What if the smaller list were sorted? Would you be able to do it then?
^ Good point. An alternative: can you find where to insert elements of the small list inside the big list in less than O(n)? (HINT: The big list is sorted.)
The question u made raised is can't possible. Basically the linked list traverse the highest value to the next node. So how it is possible?
There is no way to take the elements from the small unsorted linked list and add it to the larger sorted list. The linked list required that O(n^2) as a part of time complexity. Without reaching to the O(n^2) linked list doesn't works.
Anyways as of you learning stage, u thought a nice point. Gud. Keep it on.
The question u made raised is can't possible. Basically the linked list traverse the highest value to the next node. So how it is possible?
There is no way to take the elements from the small unsorted linked list and add it to the larger sorted list. The linked list required that O(n^2) as a part of time complexity. Without reaching to the O(n^2) linked list doesn't works.
You are wrong.
^ Agreed. Perhaps a more direct hint:
You could just take the second list and stick it on the end of the first one. Can you sort a linked list in less than O(n^2)?
Note: Answering the question this way isn't as efficient, but it has as good a time complexity as you could hope for.
If both linked lists are sorted, you can merge them in O(n). Since large linked list is already sorted. Then, all you need to do is sorting the smaller one.
Simple answer - sort your small list using an appropriate algorithm then merge them using an appropriate algorithm and of course you can sort a linked list in less than O(n^2).
How much memory are you allowed to use? Are you allowed to reorder the smaller list? Without answers to these questions, I don't see how to answer the original question.
^ Well, one could be creative. Given two linked lists, you could append them in O(n), transform to an array in O(n), sort the array in O(n*logn), and convert back to a linked list in O(n). Really there are a thousand different ways to answer this question in the affirmative, and if you're not concerned with actual efficiency but with complexity... each is as good as the last.
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.