题解 | #两个链表的第一个公共结点#

两种解法
首先需要知道一点

如果出现公共部分，很明显从第一个公共部分开始，后面都是相同的

所以要么有公共部分，要么两条链表就是组成Y型

• 1.使用set
  • 就是先遍历一条链表，然后将它的节点都给存起来，那么再遍历另一条链表的时候第一次碰到在set中存在的节点很明显就是交点了
  • 如果一直没有碰到交点，那么到最后出来循环返回null表示没有交点

    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
       if(pHead1==null||pHead2==null) return null;
      //用一个set来存一下pHead1遍历过的节点
      HashSet<ListNode> set = new HashSet<>();
      while(pHead1!=null){
          set.add(pHead1);
          pHead1 = pHead1.next;
      }
      while(pHead2!=null){
          if(set.contains(pHead2)){
              return pHead2;
          }
          pHead2 = pHead2.next;
      }
      return null;
    }

• 2.双指针法
  • 两条链表先遍历一遍，走到最后一个节点，同时记录这两条链表的长度len1,len2
    • 如果他们的最后一个节点是不同的，很明显不相交，直接返回null
    • 如果最后节点相同，那么如何找到交点？
      • 先让长的链表先走|len1-len2|步
      • 然后两个链表一起走肯定会在交点处相遇

    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if(pHead1==null||pHead2==null) return null;
        ListNode t1 = pHead1;
        ListNode t2 = pHead2;
        int len1 = 1;
        int len2 = 1;
        while(t1.next!=null||t2.next!=null){
            if(t1.next!=null){
                t1 = t1.next;
                len1++;
            }
            if(t2.next!=null){
                t2 = t2.next;
                len2++;
            }
        }
        if(t1!=t2) return null;
        //长的那个先走Math.abs(t1-t2)步
        t1 = len1>len2?pHead1:pHead2;
        t2 = t1==pHead1?pHead2:pHead1;//t1指向长链表
        for(int i = 0;i<Math.abs(len1-len2);i++){
            t1 = t1.next;
        }
        //同时走，走到相交
        while(t1!=t2){
            t1 = t1.next;
            t2 = t2.next;
        }
        return t1;
    }