detect merged linked list

[sdkumar00]

Given the pointers to 2 linked list, how will we find out if they are merged? i.e. at some point they point to the same address.

[weaknessforcats]

Can you provide an example of your problem? Exactly which pointers are ou referring to?

[sdkumar00]

We are given head pointers to 2 different linked lists. At some point both the lists have the same node pointers. How can we detect this ??

[donbock]

Pick one of the lists and traverse it from head to tail. For each node encountered, compare it to the head pointer of the other list. If you find a match then the second list is embedded within the first list.

If you don't find a match, then repeat the procedure by traversing the second list.

[weaknessforcats]

Method B:

Traverse the first list and build an array of the addresses you encounter.

Then traverse the second list and check that every address you encounter is not in the array.

This is the logic of a symbol table.

[jkmyoung]

Donbock's method is more efficient. There is also the lazier method, involving only one comparison.
Method C:
Traverse list A to the tail
Traverse list B to the tail.

Compare tails.

You lose speed by having to traverse the list, but gain speed by only having one comparison. It's probably slower for matches, but definitely faster if there is no match.

Edit: Not counting null checking as you have to do that with the other methods as well. Only counting element to element comparisons.

[Banfa]

But for Dons method what if part but not all of one list is in the other. That is if NODE C is the common node but in LIST 1 it is NODE 1A that points to NODE C and in list 2 it is NODE 2B that points to NODE C. A pity it is not easy to traverse backwards, if at some point 2 lists contain the same node they must by definition have the same tail (assuming single linkage).

Method D: Fix your software so that it does not put a single node onto more than one singly linked list at a time.

Or if it really is a part of the logic that any give node might be a part of more than 1 list but that not all nodes of necessity are part of all lists put data into each node to record which lists it is a part of. Then you have only to scan a single list once to detect nodes that are in both lists.


Actually I think to properly answer the question given you need to answer the question, how did the data get into this situation in the first place?

[jkmyoung]

Ah true; I can't believe I missed that!

There are situations where you do need reverse trees, perhaps trying to get from one place to another through different routes. Can't think of other good examples at the moment.

Then, I would use my method, as I'm lazy, and wouldn't want to implement a symbol table. If you need to find where the intersection is, use the symbol table; or use method C to figure out if you need to use a symbol table, then use method B if necessary.