Printable View
I've two Linked lists which cross. Means they have a common node after which they become one linked list giving it a Y shape. How do I determine whether there's common node in two linked lists or not.
If you put in foe loop for two linked list of lemngth m and n respectively, the complexity would come (m*n). So any optimized solution?
The answer can depend on the implementation of your lists and an ability to use extra memory.
If the question is: "do two lists merge?" then we have two options.
1. If the lists keep a pointer to the last element (most implementations do that) then clearly the complexity is O(1). One just may compare the pointers to the last element.
2. Otherwise, one has to loop through the both lists, reach their tails and compare the pointers to the last element. The comnplexity of this algorithm is O(m+n).
If the question is: "what is the first common element of two lists?", then we have two option depending on constraint on the available memory,
1. We can use O(min(m,n)) memory. If the length of lists are not known yet, then loop through them simulateneously until we find the first tail. It requires O(min(m,n)) operations. Allocate a block of memory to keep the pointers to the elements of a list. Loop through the shorter list and copy pointers to this array. Sort this array (treat pointers as integers).
Loop through the longer list and using binary serch try to find a pointer to the current element in the constructed array. Stop when a pointer to the requested element is found or the end of the second list is found.
Clearly the complexity of this final serch is O(max(m,n)*log(min(m,n)).
So the overall complexity is O(min{m,n} + min{m,n}*log(min{m,n}) + max{m,n}*log(min{m,n})) = O(max(m,n)*log(min(m,n))).
2. We are not allowed to use extra memory. Then we can't do better than O(mn) which is achieved by your algorithm
Actually, you can find the common node in O(n) time for singlely linked lists with fixed memory overhead using a little bit of linear algebra.
Step 1: Walk A and count the number of nodes. You terminate at some node C, with a count of M.
Step 2: Walk B and count the number of nodes. If you do not terminate at C, then you're done (they do not overlap!). Otherwise, you terminate at the same C with a count of N.
You can now think of this in terms of four key nodes. A, B, C, and some 'pivot' node P which is where A and B are merging into the same list. Think of this as a triangle with A, B and C at the vertices and P in the middle somewhere. Currently A->->->P->->->C and B->->->P->->->C. (We don't know the number of hops involved between (A,P), (B,P) or (P,C) at this point.)
Step 3: Reverse A. (Look up up algorithms for reversing singlely linked lists in fixed memory in O(n) if you have to.)
You now have C->->->P->->->A and B->->->P->->->A. So walk B (you MUST terminate at A) and count the nodes. Call this L.
So, now let's define three variables, x, y and z. x is the distances from A to P, y from B to P, and z from C to P.
You can now define the equations:
x + y = |A to P| + |B to P| = |A to B| - 1 = L - 1
x + z = |A to P| + |C to P| = |A to C| - 1 = M - 1
y + z = |B to P| + |C to P| = |B to C| - 1 = N - 1
So you have three variables and three equations. Solve, and you will find that:
y = (L + N - M - 1) / 2
x = L - 1 - (L + N - M - 1) / 2
z = N - 1 - (L + N - M - 1) / 2
You only actually need y, because then you can walk forward that nodes from B and you're at P.
To clean up, you can reverse from C again and you'll be back where you started.
All operations are O(n), only fixed overhead memory is used.
On further considering, I'm overcomplicated this problem significantly.
Just calculate N and M as above, and then consider which one is larger. If M > N, then walk forward in A (M-N) nodes. If N > M, then walk forward in B (N-M) nodes. Either way, it is impossible that you have walked past P at this point, as the distance you walked must have been part of either A->P or the B->P sections.
So now you have an A' and a B' such that the length from A' to C is the same as the length from B' to C, so walk forward in both lists in parallel checking each node as you go to see if you've hit P. (You need to initially check if A' == B' as well). Since you have the same number of nodes left in each list before you hit C, you're guaranteed to hit P at the same time.
I should also add the caveat that there are lots of complex situations that could arise if there was also a loop of some sort in the list, so you would ideally want to first verify that neither list has a loop initially.
Comparing the last node pointers to get an O(m+n) algorithm as has been suggested seems like a good choise.Quote:
Originally Posted by singla1105
If you can afford an extra hash-based set you can improve this to O(min(m,n)). You just loop through both lists in the same loop and insert the node pointers in the set. You stop when you reach the end of one list. During insertion, if a pointer is already in the set the lists cross. This is fast if the lists cross early or if one list is much shorter than the other. Another advantage is that you get the actual cross pointer.
But I'm going to suggest another solution. It's to reduce the problem to a cycle finding problem with a known solution,
http://en.wikipedia.org/wiki/Cycle_detection
You just imagine your two lists to be one list by considering them one after the other. When you reach the end of the first list you continue with the next list. The end of the second list constitutes the end of the combined list. If this imaginarily concatenated list has a cycle the two lists cross.
Here is the pseudo code to find the node of intersection of 2 lists:
Take two pointers at the start of both the linked lists.Find out the length for both of them. Suppose the length of the linked list are count1 and count2 respectively.
If (count1 > count2) advance the pointer of linked list 1 by count1-count2 nodes.
else advance the pointer of linked list 2 by count2-count1 nodes.
Now start advancing pointers for both the linked lists one by one and check for the first node when both the pointers are pointing to the same node. This is the node where they merge.
public static <T> int length(ListNode<T> listHead){
int listLen = 0;
ListNode<T> current = listHead;
while (current != null)
{
listLen++;
current = current.next;
}
return listLen;
}
public static <T> ListNode<T>
firstCommonNode(ListNode<T> pList1,ListNode<T> pList2)
{
int length1 = length(pList1);
int length2 = length(pList2);
if (length1 > length2)
{
for (int a=0; a < (length1-length2); a++)
{
pList1 = pList1.next;
}
}
else
{
for (int a=0; a < (length2-length1); a++)
{
pList2 = pList2.next;
}
}
while (pList1 != pList2)
{
pList1 = pList1.next;
pList2 = pList2.next;
}
return pList1;
}
Explanation: our method takes two lists as arguments. It returns true if those lists intersect and false if they don't. The first two if statements are used to check for null lists and special case where the head of one list is the end node of the other list. When there are no null or special lists, we do the following:
First while loop counts the number of nodes in the first list.
Second while loop counts the number of nodes in the second list.
After having the length of each list, we find the difference in number of nodes and then move whichever pointer that points to the longer list ahead using that difference.
Finally, the while loop is used to find the intersection. We just loop until either of the pointers reaches the end of its list. During the loop, if the pointers meet, we return true immediately because it means that the lists intersect. But at the end of the loop and nothing has happened, we simply return false because the lists don't intersect.
You may notice that the pointers will meet at the first node that both lists share! Thus, this algorithm can be tweaked a little bit to return the intersection node of two intersecting lists. Or, this algorithm can be used to break two intersecting lists at their intersection node. Pretty neat huh?
Anyway, time complexity is O(m + n) where m and n are the number of nodes in the first and second list respectively. The space complexity is O(1).