判断链表是否相交

无环

  • 解法1：扫描一遍，获取长度，然后长的那个链表先走差值，然后两个指针一起走，碰头即为相交。

  • 解法2：依次往后走，当一个指针走完了之后，重新置到另一个链表开头，当两个指针碰头，即为相交。

    有环

  • 先判断是否有环，如果两个都没环，转无环问题；如果一个有环，一个没环，则不相交；如果两个都有环，先在两个链表的环中各自找到一个节点A,B，然后从A构建快慢指针，看再次相遇之前，慢指针是否能等于B节点。

    获取链表第一个相交节点

    无环

  • 解法1：扫描一遍，获取长度，然后长的那个链表先走差值，然后两个指针一起走，碰头即为第一个相交节点。

  • 解法2：依次往后走，当一个指针走完了之后，重新置到另一个链表开头，当两个指针碰头，即为第一个相交节点。

    有环

  • 解法1：扫描一遍，记录不同节点数目（开额外空间，hashmap），然后长的链表走差值，然后两个指针一起走，碰头即为第一个相交节点。

  • 解法2：根据判断链表是否相交，找到公共节点，把公共节点作为尾结点，走一遍解法1的流程。