Description

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

Example 1:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,0,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

Example 2:

Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Reference of the node with value = 2
Input Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [0,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

Example 3:

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: null
Input Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.

Notes:

If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.

Solution1 - Hashset

先将一个链表中的所有值都分别存到HashSet中，再遍历另一个链表，当第一次找到存在于哈希表中的节点时，这个节点就是两链表的交叉点。

如果遍历到这个链表的尾部时，仍然没有找到有任何节点存在于哈希表中，则表明两链表没有交叉点（于是 return null）。

时间复杂度 O(m)+O(n)，空间复杂度 O(m)。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null)
            return null;
        
        Set<ListNode> set = new HashSet();
        ListNode node = headA;
        while(node != null){
            set.add(node);
            node = node.next;
        }
        
        node = headB;
        while(node !=null){
            if(set.contains(node))
                return node;
            node = node.next;
        }
        return null;
        
    }
}

Solution2 - 表连接法

将第一个表的尾与第二个链表的头相连，自然就成了带环链表，然后的问题就是求出带环链表的环起始节点了，这个可以参考问题带环链表。

由于题目要求不改变表结构，所以最后恢复表结构即可。

Solution3 - 双指针法

时间复杂度 O(m+n)，空间复杂度 O(1)。

public class Solution {
   public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if( headA == null || headB == null)
            return null;
        
        ListNode p1 = headA;
        ListNode p2 = headB;
        while(true){   
            if(p1 == p2 && p1==null)
                return null;
            if(p1 == p2 && p1!=null)
                return p1;
            
            p1 = p1.next;
            p2 = p2.next;
            
            if(p1 == p2 && p1==null)
                return null;
            if(p1 == null)
                p1 = headB;
            if(p2 == null)
                p2 = headA;       
        }
    }
}

Solution4 - 速度最快且不用辅助空间的一种方法

先分别求出AB两个链表的长度（lenA 和 lenB），然后用较长的那个链表的长度减去较短的那个链表的长度，以求出长度的差值（diff）。

对较长的那个链表先跑 diff 的长度，此后，两个链表同时递增，当遇到相同的节点时，如果这个节点为 null，则两链表无交集，否则为交叉节点。

时间复杂度 O(m)+O(n)，空间复杂度 O(1)。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB ==null)
            return null;
    
        int lenA = getLen(headA);
        int lenB = getLen(headB);
        
        int diff = Math.max(lenA, lenB) - Math.min(lenA, lenB);
        ListNode startNode1 = lenA > lenB?headA:headB;
        ListNode startNode2 = startNode1==headA?headB:headA;
    		
      	//有可能出现两链表长度相等的情况，此时下面这部分while不执行
        while(diff!=0){
            startNode1 = startNode1.next;
            diff--;
        }
    
        while(true){
            if(startNode1 == startNode2 && startNode1 != null)
                return startNode1;
            if(startNode1 == startNode2 && startNode1 == null)
                return null;
            
            startNode1 = startNode1.next;
            startNode2 = startNode2.next;            
        }    
        
    }
    private int getLen(ListNode head){
        int count = 0;
        ListNode node = head;
        while(node!=null){
            count++;
            node = node.next;
        }
        return count;
    }
}

Reference

LeetCode 160 Intersection of Two Linked Lists（链表相交）（Linked List）（*） - https://blog.csdn.net/nomasp/article/details/50572819
LeetCode 160. Intersection of Two Linked Lists - https://www.jianshu.com/p/7f61be95685c
[LeetCode] Intersection of Two Linked Lists 求两个链表的交点 - https://www.cnblogs.com/grandyang/p/4128461.html

[刷题] LinkedList - Leetcode - 160 Intersection of Two Linked Lists