merged linked list in C

Question

Hello,

This question was asked to me in an interview: There are two header of two linked lists. There is a merged linked list in c where in the second linked list is merged into the first one at some point. How could we identify the merging point and what is the complexity of finding that point ?

Could anybody please help?

Answer 1

O(n)

search = list1->header;
if (mixed->header == list1->header) search = list2->header;

while (mixed->next != search) mixed = mixed->next;

---

Edit: new name for variables and a few comments

/* search is what we want to find. Here it's the head of `list2` */
search = list2->header;
/* unless the merging put `list2` first; then we want to search for `list1` */
if (mixed->header == list2->header) search = list1->header;

/* assume (wrongly) that the header for the mixed list is the merge point */
mergepoint = mixed->head;

/* traverse the mixed list until we find the pointer we're searching */
while (mergepoint->next != search) mergepoint = mergepoint->next;
/* mergepoint now points to the merge point */

Answer 2

Update: This assumes the Y-shaped joining of two linked lists as described better in Steve Jessop's post. But I think the description of the problem is sufficiently ambiguous that various interpretations are possible, of which this is only one.

---

This can be done with a single pass through one list plus a partial pass through the other. In other words, it's O(n).

Here's my proposed algorithm:

Create a hashmap. (Yes, this is busywork in C if you don't have a library handy for it). The keys will be pointers to the items in List1 (i.e. the head pointer and each link). The values will be integers denoting the position, i.e. distance from the head of List1.

Run through List1, keeping track of the position, and hash all your pointers and positions.

Run through List2, keeping track of the position, and find the first pointer that occurs in the hashmap.

At this point, you'll know the position in List2 of the first node common to both lists. The hashmap entry will also contain the position in List1 of that same node. That will nicely identify your merge point.

Answer 3

Do you mean you have a Y-shape, like this:

list1: A -> B -> C -> D -> E -> F

list2: X -> Y -> Z -> E -> F

Where A .. Z are singly-linked list nodes. We want to find the "merge point" E, which is defined to be the first node appearing in both lists. Is that correct?

If so, then I would attach the last node of list2 (F) to the first node of list2 (X). This turns list2 into a loop:

list2 : X -> Y -> Z -> E -> F -> X -> ...

But more importantly:

list1 : A -> B -> C -> D -> E -> F -> X -> Y -> Z -> E -> ...

This reduces the question to a previously-solved problem, which can be solved in O(n) time and O(1) additional storage.

But reading your question, another possibility is that by "merge" you mean "insert". So you have two lists like this:

list1: A -> B -> C

list2: D -> E -> F

and then another completely separate list:

list3: A -> B -> D -> E -> F -> C

where this time, A .. F are the values contained in the list, not the nodes themselves.

If the values are all different, you just need to search list3 for D (or for the later of D and A, if you don't know which list it was that was copied into the other). Which seems like a pointless question. If values can be repeated, then you have to check for the full sequence of list2 inside list3. But just because you find "DEF" doesn't mean that's where list2 was inserted - maybe "DEF" already occurred several times in list1 beforehand, and you've just found the first of those. For instance if I insert "DEF" into "ABCDEF", and the result is "ABCDEFDEF", then did I insert at index 3 or at index 6? There's no way to tell, so the question can't be answered.

So, in conclusion, I don't understand the question. But I might have answered it anyway.

Answer 4

< edit > this assumes a linear merge, not a Y... since that jerk carl interpreted it differently than I, and I was stealing his answer.. jackass. ;)

< /edit >

If you are linking the items in by just moving pointers, you can index those pointers as indicated by Carl Smotricz to achieve a search solution that is O(n + 1) in time with regard to the length of the first list. The reason why it is only the first list is because pointer value determines membership of a list, so i can tell in O(1) time which original list the object belonged to, and as soon as i find a 2-nd list member, I am done. In the worst case, the list is appended to the end of the first list. This assumes a constant-time hash for the pointers. Total run-time of indexing, merging, and searching would be O(2n + m + 1), n is length of list 1, m is length of list 2.

< edit >

it occurs to me that you don't need to index the whole of the lists; just remember the head of the 2nd list, and look for that in the merged list. Search time would be O(n + 1). Time to merge and search would then be O(2n), assuming you can keep a tail pointer to the 2nd list. < / edit>

If instead you are instead merging the lists by creating copies of the elements, you will have to use a string comparison algorithm, where in this case your string isn't composed of characters but rather of objects. Linear-time string coparison algorithms exist. One of the simplest is called the z-algorithm. Total run-time for this search would be O(n + m) because you must look at the entire second list, and possibly all of the first. Total run-time for merging and searching would be O(2n + 2m)

< edit > I forgot... There is also overhead in the Z algorithm in prepending string 2 to string 1 so that you can find your pattern. This adds an additional O(m) time.

In a radically over-engineered solution, you could build a suffix tree out of your merged list in O(n + m) time using Ukkonen's algorithm and search for the 2nd list in O(m) time. < /edit >

Answer 5

If the question means list2 contained in list1 (that is list2 points somewhere in the middle of list1), then it is easy - just walk list1 and compare pointers until you reach list2.

However such interpretation does not make much sense, because by inserting list2 into the list1 (like 1 1 2 2 1), you would also modify list2 - the last 1 becomes part of list2.

So I will assume the question is about the Y shape:

list1: A -> B -> C -> D -> E -> F

list2: X -> Y -> Z -> E -> F

This can be solved using hashtable as Carl suggested.

Solution without a hashtable would be this:

1. Walk list1 and disconnect all its pointers as you go
2. Walk list2. When it ends, you've reached the junction point
3. Repair the pointers in list1

Disconnecting and repairing pointers in list1 can be done easily using recursion:

Diconnect(node)
{
    if (node->next == NULL)
      walk list2 to its end, that is the solution, remember it
    else
    {
       tmp = node->next;
       node->next = NULL;
       Disconnect(tmp);
       node->next = tmp;  // repair
    }
}

Now call Disconnect(list1).

That is recurse down list1 and disconnect pointers. When you reach end, execute step 2 (walk list2 to find junction), repair pointers when returning back from recursion.

This solution modifies list1 temporarily, so it is not thread safe and you should use a lock around the Disconnect(list1) call.

Answer 6

Sorry if my answer seems too simple, but if you have two linked list which are identified by a header and you join them, so that

A -> B -> C -> D is the first list, and

1 -> 2 -> 3 -> 4 is the second, then suppose

A -> B -> C -> 1 -> 2 -> 3 -> 4 -> D is the result

then to find the merging point you need to go through the final list until you find the second header (the 1). Which goes in O(n1) worst case, where n1 is the number of elements of the first list (this happens if the second list is merged at the end).

That's how I would intend the question. The reference to the C language would probably mean that you have no 'object' or pre-packaged data structure, unless specified.

[update] as suggested by Sebastian, if the two list above have the same elements my solution won't work. I suspect that this is where the C language comes into action: you can search for the address of the first element of the second list (the head). Thus the duplicates objection won't hold.