- Forum
- General C++ Programming
- Merge a linked list with another linked
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.
code:
https://pastebin.com/2PaKHHE3
code:
https://pastebin.com/2PaKHHE3
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?
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).
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).
Not like std::list::merge that produces a sorted list from sorted lists.
With head and tail that should be O(1).
Topic archived. No new replies allowed.