434,720 Members | 2,237 Online + Ask a Question
Need help? Post your question and get tips & solutions from a community of 434,720 IT Pros & Developers. It's quick & easy.

Find the node where 2 lists merge

 P: n/a Hello all, I have a data structures problem. Assume there are 2 linked lists L1 and L2. They merge into some node. L1 1->2->3->4->5->6 / L2 8->7->9->/ L1 and L2 merge in node with value 5. We need to return the pointer to the node with value 5. What is the best and efficient solution to find the node where the 2 lists merge? Thanks, Anunay Apr 21 '06 #1
9 Replies

 P: n/a an*********@gmail.com said: Hello all, I have a data structures problem. Assume there are 2 linked lists L1 and L2. They merge into some node. L1 1->2->3->4->5->6 / L2 8->7->9->/ L1 and L2 merge in node with value 5. We need to return the pointer to the node with value 5. What is the best and efficient solution to find the node where the 2 lists merge? mergenode = 0; while(l1 && l2 && mergenode == 0) { ++l1->count; ++l2->count; if(l1->count == 2) { mergenode = 1; /* l1 points to node at merge point */ } else if(l2->count == 2) { mergenode = 2; /* l2 points to node at merge point */ } else { l1 = l1->next; l2 = l2->next; } } -- Richard Heathfield "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: rjh at above domain (but drop the www, obviously) Apr 21 '06 #2

 P: n/a Hi Richard, Can you please explain me the logic of the above code? Thanks, Anunay Apr 26 '06 #3

 P: n/a an*********@gmail.com opined: Hi Richard, Richard who? Can you please explain me the logic of the above code? There's no code above. Please quote context (what you're replying to, and who said it). Read the link in my sig. -- "Oh, I've seen copies [of Linux Journal] around the terminal room at The Labs." (By Dennis Ritchie) Apr 26 '06 #4

 P: n/a Vladimir Oka opined: an*********@gmail.com opined: Hi Richard, Richard who? Ooops. Apologies. Didn't think it'd sound like this. :-( -- "Computers may be stupid, but they're always obedient. Well, almost always." -- Larry Wall (Open Sources, 1999 O'Reilly and Associates) Apr 26 '06 #5

 P: n/a [Sorry to reply to my own article, but an explanation of the logic of my code has been requested. First, the problem statement (abbrev'd).] Richard Heathfield said: an*********@gmail.com said: What is the best and efficient solution to find the node where the 2 lists merge? We will have two pointers, and start them off at the beginnings of the two branches. If the branches merge, we need a pointer to one or other of them. We begin by assuming that each list is terminated by a null pointer, and that every node on each list has an int field, count, which is initially set to 0. If you like, think of it as being unpainted. If, during our travels, our first pointer hits it, we'll add 1 to it (paint it blue). If our second pointer hits it, we'll add 1 to it (paint it yellow). If, after such an addition, the count value is 2 (painted blue+yellow=green), we have just been processing a node that is in both lists. Since we have not yet encountered such a node, this must be the first merge point. So imagine two paintbrushes, each one travelling down its own branch of the list, one painting a blue stripe and the other painting a yellow stripe. As soon as we detect green, we stop, and our paintbrush is hovering right over the merge point. Here is the code again: mergenode = 0; while(l1 && l2 && mergenode == 0) { ++l1->count; ++l2->count; if(l1->count == 2) { mergenode = 1; /* l1 points to node at merge point */ } else if(l2->count == 2) { mergenode = 2; /* l2 points to node at merge point */ } else { l1 = l1->next; l2 = l2->next; } } -- Richard Heathfield "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: rjh at above domain (but drop the www, obviously) Apr 26 '06 #6

 P: n/a Here's another solution that came to mind.. Not exactly very efficient, but i find it easy to think recursively... struct node * commonnode( struct node * ptr1, struct node * ptr2) { struct node * common; if (ptr1==ptr2) /* Common node found.. This may be null too.. that meas actually no common node */ return ptr1; if (!ptr1 || !ptr2) return NULL ; /* If one of them is null, no chance of having a common node*/ common = commonnode(ptr1->next, ptr2); if (common) /* Some common node found */ return common; return commonnode(ptr1,ptr2->next); } Apr 26 '06 #7

 P: n/a >L1 1->2->3->4->5->6 /L2 8->7->9->/ L1 and L2 merge in node with value 5. We need to return the pointer tothe node with value 5.What is the best and efficient solution to find the node where the 2lists merge? one more solution is possible if the linked lists are read only and we can't have a counter traverse through L1..let its length be m+l (l is the length of common part of the linked list) similarly L2 has length n+l subtract both you will get m-n if it is positive L1 has m-n nodes more than L2 traverse these many nodes on L1. now L1 and L2 has same number of nodes till end. go on incrementing and comparing the nodes , you will get the point where both the lists are merging regards jitendra. Apr 26 '06 #8

 P: n/a Amit Bhatnagar wrote: Here's another solution that came to mind.. Not exactly very efficient, but i find it easy to think recursively... You have already been told that you need to include context. Without it your article is simply meaningless blather to most readers. Google is not usenet, so act accordingly. See below for means. -- "If you want to post a followup via groups.google.com, don't use the broken "Reply" link at the bottom of the article. Click on "show options" at the top of the article, then click on the "Reply" at the bottom of the article headers." - Keith Thompson More details at: Also see Apr 26 '06 #9

 P: n/a I could think of a better solution... Its complexity is: O(length of longer list) The funda is : if lengths of both lists are equal, then we can just keep on moving the pointers ptr1 and ptr2 and comparing them each time till we reach a common node or null. If the lengths are unequal, reduce the problem in terms of comparing the list with equal number of nodes by moving the pointer to the longer list till the number of nodes in the resulting lists are equal.. Here's some code for above logic: struct node * commonnode( struct node * ptr1, struct node * ptr2) { int l1,l2; l1=listlength(ptr1), ; l2=listlength(ptr2); /* calculating Length of a list is trivial; can be done in O(n) time if n nodes are there*/ for (int i=0;i< l1-l2;i++) ptr1=ptr1->next; for (int i=0;i< l2-l1;i++) ptr2=ptr2->next; /* Moving the pointer to longer list till the length of remaining list equals thatt of shorter list; above loops have no effect on shorter list */ /* Now we have equal nodes in the lists pointed to by ptr1 and ptr2*/ while (ptr1 && ptr2) /*Continue as long as one of them is null*/ { if (ptr1==ptr2) return ptr1; /* Common node found.. */ ptr1=ptr1->next; ptr2=ptr2->next; } /* No common node :-( Return NULL */ return NULL; } Apr 26 '06 #10

This discussion thread is closed

Replies have been disabled for this discussion. 