题意：给定两个链表A、B的表头节点，找到链表交叉节点（地址值相同）。链表A长度为m，链表B长度为n，范围在[1, 3e4]
题解1：
根据哈希表去重的原理，使用哈希表集合HashSet来维护链表节点，默认比较节点地址值。将链表A中的节点全部add进HashSet中，然后遍历链表B中的节点，如果发现某节点在HashSet存在则找到交叉节点。
时间复杂度：O(n + m)
空间复杂度：O(m)
HashSet实现代码
/**
* 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) {
Set<ListNode> set = new HashSet<>();
while(headA != null) {
set.add(headA);
headA = headA.next;
}
while(headB != null) {
if(set.contains(headB)) {
return headB;
}
headB = headB.next;
}
return null;
}
}
题解2：
维护链表A指针pA，链表B指针pB
这两个指针分别从链表头开始往后遍历，遍历到表尾后则指向另一个链表头继续遍历，直至找到交叉节点，或者两个指针同时再次遍历到表尾。
PS：当两个指针都指向另一个链表时，就表明，两个指针当前所在位置距离表尾的长度是一致的，通过这种方式可以消除两个链表长度不统一。
时间复杂度：O(m+n)
空间复杂度：O(1)
双指针实现代码
/**
* 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) {
ListNode pA = headA, pB = headB;
while(pA != null || pB != null) {
if(pA == pB) return pA;
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return null;
}
}