[数据结构与算法]判断两个链表是否相交

判断两个链表是否相交

题目描述

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。

链表

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

解决方案

一：使用HashSet的元素不重复性

       遍历第一条链表，将第一个链表的所有数据全部都保存到
     HashSet中,然后在遍历另一条链表，每一次遍历元素的过
     程中，都使用hash的contains方法判断是否与之前的重复

优点：利用了set的不可重复性，容易思考到

缺点：时间复杂度为O(m + n)

代码如下所示

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;
            }
            headB = headB.next;
        }
        return null;

    }

二、使用两个指针同时遍历

1、当有一个链表为空时不可能相交

2、 使用两个指针同时遍历两条列表

    将头结点headA赋值给a
    将头结点headB赋值给b
     while( a!=b){
        a = a == null?headB:a.next;
        b = b == null?headA:b.next;
    }
   返回值为a或者b

解释：

     在两个链表都不为空时分为两大种情况：
  一：两个链表长度一样
        1、相交
           两个两个指针同时到达相交的节点，直接a==b,返回
           相交节点
        2、不相交
           两个节点同时到达尾端，都为Null，a==b,返回null
  二、两个节点长度不一样
         1、相交
            假设a的长度为 x + z
            假设b的长度为 y + z
            当a遍历到 x + z + y的长度时 b遍历到了 y + z + x的长度，
               也符合了a == b的条件了
         2、不相交
            假设a的长度为 x
            假设b的长度为 y
            当a遍历到 x + y的长度时 b遍历到了 y  + x的长度，
               也符合了a == b == null的条件了

优点：时间复杂度为O(1)

缺点：难思考

代码实现

 public ListNode getIntersectionNode2(ListNode headA, ListNode headB){
        if (headA == null || headB == null){
            return null;
        }
         ListNode tempA = headA;
         ListNode tempB = headB;
         while(tempA != tempB){
             tempA = tempA == null?headB:tempA.next;
             tempB = tempB == null?headA:tempB.next;
         }
         return tempA;
    }