CC--Q2.7

2.7 Intersection: Given two (singly) linked lists, determine if the two lists intersect. Return the intersecting node. Note that the intersection is defined based on reference, not value. That is, if the kth node of the first linked list is the exact same node (by reference) as the jth node of the second linked list, then they are intersecting.

Determining if there's an intersection.

How would we detect if two linked lists intersect? One approach would be to use a hash table and just throw all the linked lists nodes into there. We would need to be careful to reference the linked lists by their memory location, not by their value.
There's an easier way though. Observe that two intersecting linked lists will always have the same last node. Therefore, we can just traverse to the end of each linked list and compare the last nodes.
How do we find where the intersection is, though?

Finding the intersecting node.

Finding the intersecting node.
One thought is that we could traverse backwards through each linked list. When the linked lists "split'; that's the intersection. Of course, you can't really traverse backwards through a singly linked list.
If the linked lists were the same length, you could just traverse through them at the same time. When they collide, that's your intersection.

Paste_Image.png

When they're not the same length, we'd like to just "chop oW-or ignore-those excess (gray) nodes.
How can we do this? Well, if we know the lengths of the two linked lists, then the difference between those two linked lists will tell us how much to chop off.
We can get the lengths at the same time as we get the tails of the linked lists (which we used in the first step to determine if there's an intersection).

Putting it all together.

1. Run through each linked list to get the lengths and the tails.
2. Compare the tails. If they are different (by reference, not by value), return immediately. There is no intersection.
3. Set two pointers to the start of each linked list.
4. On the longer linked list, advance its pointer by the difference in lengths.
5. Now, traverse on each linked list until the pointers are the same.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null I I headB == nUll) return null;
    //Get tail and compare it. 
    if(getTail(headA)!=getTail(headB)) return null;
    ListNode p1 = headA, p2 = headB;
    int len1 = 0, len2 = 0;
    while (p1 != null) {
        p1 = p1.next;
        len1++;
    }
    while (p2 != null) {
        p2 = p2.next;
        len2++;
    }
    p1 = headA;
    p2 = headB;
    if (len1 > len2) {
        for (int i = 0;i < len1 - len2; i++) {
            p1 = p1.next;
        }
    } else {
        for (int i = 0;i < len2 - len1; i++) {
            p2 = p2.next;
        }
    }
    while (p1 != p2) {
        p1 = p1.next;
        p2 = p2.next;
    }
    return p1;
    }

    ListNode getTail(ListNode){
      //ToDo...
      //return tail of the node
    }
}