Merge a linked list with another linked list O(1)?

I am supposed to merge one linked list with another linked last so that the first linked list is empty. My prof want's it to run in O(1) time but how is that possible? I feel like I'd need a loop to access each node in the linked list.

O(1)? I has to be related to n.
Well, it's a doubly linked list so I think that's why it has to be O(1).
Suppose you have two actual chains, made of rings of metal linked together.
If you wanted to join them so you have a single chain, what would be the quickest way to do it?
A) Open every link in chain B and extend chain A one link at a time by closing an open link around the final closed link of A.
B) Open the last link of chain A and, without taking it off its chain, close it around the first link of chain B.

Can you transport this analogy back to your problem?
Last edited on
O(1) is constant time.

Clearly it takes more time to merge very long lists than it does very small links, irrespective of how they're organized. So it can't be O(1).
Apparently "merge" as in "concatenate", "append", or "transfer content".
Not like std::list::merge that produces a sorted list from sorted lists.

With head and tail that should be O(1).
Registered users can post here. Sign in or register to post.