22. 相交链表（链表/160）

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
假设：整个链式结构中不存在环；函数返回结果后，链表必须 保持其原始结构；
intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
listA 中节点数目为 m；
listB 中节点数目为 n；
1 <= m, n <= 3 * $(10)^4$；
1 <= Node.val <= $(10)^5$；
0 <= skipA <= m；
0 <= skipB <= n；
如果 listA 和 listB 没有交点，intersectVal 为 0；
如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]。
示例：输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3；输出：Intersected at ‘8’。

【分析】
链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。
链表的本质就是它的数据结构存在一个变量存储下一个同类型变量（或可能为其地址），注意看下面ListNode的定义，非常重要！！！
链表是一种抽象的结构，代码中看不到整个表，只能看到两两结点之间的关系。
由答案可知假设，如果两链表相交，相交以后就不再分开
方法1：哈希集合
先遍历链表A，把所有A的结点记录在HashSet；后遍历链表B，遇到已存在哈希表中的结点就返回出去。
这种方法时间复杂度O(m+n)，空间复杂度O(m)。
方法2：双指针法
如果 A 到达链表 A 的末尾（null），则将其重定向到链表 B 的头节点 headB。
如果 B 到达链表 B 的末尾（null），则将其重定向到链表 A 的头节点 headA。
设链表 A 的非公共部分长度为 a，链表 B 的非公共部分长度为 b，公共部分长度为 c。
指针 A 走过的路径：a + c + b。
指针 B 走过的路径：b + c + a。
两者路径长度相同，因此会在相交点相遇。
该方法时间复杂度O(m+n)，空间复杂度O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;// 存储节点的数据值
 *     public ListNode next;// 指向链表中下一个节点的引用
 *     public ListNode(int x) // 构造函数，用于创建一个新的ListNode实例
 *     { 
 *        val = x; // 初始化节点的数据值为x
 *     }
 * } 
 */
public class Solution {
	//哈希集合
	public ListNode GetInterscetionNode1(ListNode headA, ListNode headB){
		HashSet<ListNode> hashSet=new HashSet<ListNode>();
		while(headA!=null){
			hashSet.Add(headA);
			headA=headA.next;
		}
		while(headB!=null){
			if(hashSet.Contains(headB)){
				return headB;
			}
			headB=headB.next;
		}
	}
	
	//双指针法
    public ListNode GetIntersectionNode2(ListNode headA, ListNode headB) {
        ListNode ap=headA, bp=headB;
		while(ap!=bp){
			ap=ap==null?headB:ap.next;
			bp=bp==null?headA:bp.next;
		}
		return ap;
    }
}