|
-
January 16th, 2013, 02:14 AM
#6
Re: Find a common node in two Linked lists
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).
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|