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;
    }
}