LeetCode每日一题：相交链表

首先介绍一下我想到的暴力解法把，代码是使用HashSet实现的，先把第一个链表中的数据都加入到HashSet中，然后再把第二个链表中的数据进行逐一比较，如果有重复的就返回，没有的话就返回null
时间复杂度 : O(m+n)
空间复杂度 : O(m)或 O(n)

• 代码实现;

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

第二种解法：双指针法
大体思路就是让他们走过的路程变成相等的，利用了遍历链表a+遍历链表b所需要走的路程是一样的，但是遍历a和b的顺序可以不一样，若相交，链表A： a+c, 链表B : b+c. a+c+b+c = b+c+a+c 。则会在公共处c起点相遇。若不相交，a +b = b+a 。因此相遇处是NULL。图解：

• 代码实现：

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
ListNode pA = headA, pB = headB;
while (pA != pB) {
    pA = pA == null ? headB : pA.next;
    pB = pB == null ? headA : pB.next;
}
return pA;
}

题解下面的评论是真的妙啊，这年头算法题也能这么文艺吗