How to merge two linked lists in O(1) time in c?

Question

Given two lists l1,l2, show how to merge them in O(1) time. The data structures for the lists depends on how you design it. By merging I mean to say union of the lists.

Eg: List1 = {1,2,3} List2 = {2,4,5}

Merged list = {1,2,3,4,5}

Answer 1

On "merging" two sorted lists

It is straightforwardly impossible to merge two sorted lists into one sorted list in O(1).

About the closest thing you can do is have a "lazy" merge that can extract on-demand each successive element in O(1), but to perform the full merge, it's still O(N) (where N is the number of elements).

Another close thing you can do is physically join two lists ends to end into one list, performing no merge algorithm whatsoever, such that all elements from one list comes before all elements from the other list. This can in fact be done in O(1) (if the list maintains head and tail pointers), but this is not a merge by traditional definition.

---

On set union in O(1)

If the question is about what kind of set representation allows a union operation in O(1), then yes, this can in fact be done. There are many set representation possible in practice, each with some pluses and minuses.

An essential example of this specialized representation is the disjoint-set data structure, which permits a O(α(n)) amortized time for the elementary Union and Find operations. α is the inverse of the Ackermann function; where as the Ackermann function grows extremely quickly, its inverse α grows extremely slowly. The disjoint-set data structure essentially offers amortized O(1) operations for any practical size.

Note that "disjoint" is a key here: it can not represent two sets {1, 2, 3} and {2, 4, 5}, because those sets are not disjoint. The disjoint set data structure represents many sets (not just two), but no two distinct set is allowed to have an element in common.

Another highly practical set representation is a bit array, where elements are mapped to bit indices, and a 0/1 indicates absence/presence respectively. With this representation, a union is simply a bitwise OR; intersection a bitwise AND. Asymptotically this isn't the best representation, but it can be a highly performant set representation in practice.

Answer 2

What you are looking for is not an algorithm to merge two "lists" in O(1) time. If you read "lists" as "linked lists" then this cannot be done faster than O(n).

What you are being asked to find is a data structure to store this data in that supports merging in O(1) time. This data structure will not be a list. It is still in general impossible to merge in "hard" O(1) time, but there are data structures that support merging in amortized O(1) time. Perhaps the most well-known example is the Fibonacci Heap.

Answer 3

You make use of the fact that a PC is a finite state machine with 2^(bits of memory/storage space) states and thereby declare everything O(1).

Answer 4

Hi, I am not that experienced so please do not hit me hard if I say something stupid.

Will this work ? Since you have two linklists how about you connect on the last element of the first list the first element of the second list ? We are still talking about pointers right ? the pointer of the last element of the list is now pointing to the first element of the second list.

Does this work ?

Edit : but we are looking for the union. so I guess it wont...