Finding Intersection point of two linked list?

Question

Most of sites present this solution(see Method 3 at http://www.geeksforgeeks.org/write-a-function-to-get-the-intersection-point-of-two-linked-lists/ )

1) Get count of the nodes in first list, let count be c1.

2) Get count of the nodes in second list, let count be c2.

3) Get the difference of counts d = abs(c1 – c2)

4) Now traverse the bigger list from the first node till d nodes so that from here onwards both the lists have equal no of nodes.

5) Then we can traverse both the lists in parallel till we come across a common node. (Note that getting a common node is done by comparing the address of the nodes)

My understanding is above solution wont work if first node itself is merging node. Say list1 has 5 elements and list2 has 3 elements where element1 is the merging point. As per above algo, difference count is 2. so first we will traverse the first 2 nodes in list1. starting from 3 elementin list, traverse element feom each list one by one. So i will never get the merging point. Is n't it?

My Proposed Solution:

1)Traverse thru list1.

2) Put each element memory address(with System.identitityHashMap) in hash based data structure

3)Traverse thru list2.Get the memory address of each element and see if its exist in hashmap. If yes its the merging point.

UPDATE :- Input is

list1 = 1 -> 3 -> 5 -> 6 -> 7

list2 = 1 -> 4 -> 5

As per solution suggested in link difference in size is 2. First traverse up to 3 in list1, then compare 5 -> 6 -> 7 with 1 -> 4 -> 5. So merging point 1 is missed here.

Answer 1

My understanding is above solution wont work if first node itself is merging node

Your understanding is incorrect, provided approach will work. Considering your example :

list1 = 1 -> 2 -> 3 -> 4 -> 5

list2 = 3 -> 4 -> 5 and node 3 is the intersection.

the difference d = 5 - 3 = 2,

after step 4) list1 will be forwarded by 2 and will point to 3 -> 4 -> 5, so it will point to exactly same node as list2, which will be revealed by first comparison perfromed at step 5).

Since you implement this in Java, to compare "element memory address" (from your proposal) you simply compare references, which will give you equality only if they refer ("point to") the same object.

Hope that helps.

Answer 2

Well, this could be as simple as checking the root nodes of both the lists for equality, if the nodes are equal, that is your merging point.

Answer 3

I think the major misunderstanding here is about what is intersection point. If we look into the diagram given there and the rule stating clearly as it should be forming an inverted Y shaped list, it should mean that the nodes starting from intersection point onwards should all be merged and lead to one and only one path till the end. Something like this:

[a1] -...- [aD] - [a(D+1)] -...- [a(D+n)] 
                                       \  
                                        [ab1] - [ab2] - [ab3] - ...
                                       /
                    [b1] - ... -   [bn] 

Further, you can take out the step 3 and use a more concise approach as shown below:

public ListNode getIntersectionNode(ListNode a, ListNode b) {
    int len1 = getLengthOfSLL(a);
    int len2 = getLengthOfSLL(b);

    // Make a and b equidistant from the intersecting node.
    while (len1 > len2){
        a = a.next;
        len1--;
    }
    while (len1 < len2){
        b = b.next;
        len2--;
    }
    // Advance them together towards the intersection point
    while (a != b){
        a = a.next;
        b = b.next;
    }
    return a;
}
public int getLengthOfSLL(ListNode head){
    int len = 0;
    while (head != null){
        len++;
        head = head.next;
    }
    return len;
}