day13 leetcode-hot100-22（链表1）

160. 相交链表 - 力扣（LeetCode）

1.哈希集合HashSet

思路

（1）将A链的所有数据存储到HashSet中。

（2）遍历B链，找到是否在A中存在。

具体代码

/*** 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) {HashSet<ListNode> set = new HashSet<>();while(headA!=null){set.add(headA);headA=headA.next;}while(headB!=null){if(set.contains(headB)){return headB;}else{headB=headB.next;}}return null;}
}

2.双指针

思路

（1）如果A和B相交，那么假设相交的部分为c，不相交的部分分别为a和b。

（2）我们用两个指针分别从A链与B链开始遍历，如果遍历到尾部就从另一条链再遍历。

（3）以A链为例，其走过的路：a+c+b再次到c

（4）以B链为例，其走过的路：b+c+a再次到c

以上述结论为基础，我们可以判断节点A与节点B是否相等，如果相等则返回，如果不相等最后都输出null，然后结束。

具体代码

/*** 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!=pB){pA = pA==null ? headB:pA.next;pB = pB==null ? headA:pB.next;}return pA;}
}