473,320 Members | 1,950 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

detect merged linked list

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.
Apr 24 '10 #1
7 2300
weaknessforcats
9,208 Expert Mod 8TB
Can you provide an example of your problem? Exactly which pointers are ou referring to?
Apr 24 '10 #2
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 ??
Apr 24 '10 #3
donbock
2,426 Expert 2GB
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.
Apr 24 '10 #4
weaknessforcats
9,208 Expert Mod 8TB
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.
Apr 25 '10 #5
jkmyoung
2,057 Expert 2GB
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.
Apr 27 '10 #6
Banfa
9,065 Expert Mod 8TB
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?
Apr 27 '10 #7
jkmyoung
2,057 Expert 2GB
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.
Apr 27 '10 #8

Sign in to post your reply or Sign up for a free account.

Similar topics

11
by: C++fan | last post by:
Suppose that I define the following class: class example_class{ public: example_class(); void funtion_1(); void function_2(); protected:
5
by: Dream Catcher | last post by:
1. I don't know once the node is located, how to return that node. Should I return pointer to that node or should I return the struct of that node. 2. Also how to do the fn call in main for that...
10
by: Kent | last post by:
Hi! I want to store data (of enemys in a game) as a linked list, each node will look something like the following: struct node { double x,y; // x and y position coordinates struct enemy...
6
by: Steve Lambert | last post by:
Hi, I've knocked up a number of small routines to create and manipulate a linked list of any structure. If anyone could take a look at this code and give me their opinion and details of any...
7
by: who be dat? | last post by:
I need some help here. I'm creating a list on a page where the list is created from a dataset with two tables linked with a datarelation. The first table is a list of groups while the second...
2
by: Welie | last post by:
I apologize if this is a faq. I searched for about 45 minutes and didn't find a good answer but there are many matching posts. I have a form which is based on a simple query to a linked table....
12
by: joshd | last post by:
Hello, Im sorry if this question has been asked before, but I did search before posting and couldnt find an answer to my problem. I have two classes each with corresponding linked lists, list1...
11
by: Jonathan Wilson | last post by:
Is there some way I can do something like this #if <running on Visual C++ 2005 SP1> //SP1 code here #else //other code here #endif
0
by: Atos | last post by:
SINGLE-LINKED LIST Let's start with the simplest kind of linked list : the single-linked list which only has one link per node. That node except from the data it contains, which might be...
7
by: QiongZ | last post by:
Hi, I just recently started studying C++ and basically copied an example in the textbook into VS2008, but it doesn't compile. I tried to modify the code by eliminating all the templates then it...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.