两个单链表相交的一系列问题

目录

一、总体描述

二、细分

1、判断链表带环函数的设计

①思路1：哈希表

②思路2：快慢指针

2、分类讨论

①两个单链表都无环

②一个链表带环，一个链表不带环

③两个链表都带环

三、最终代码

---

一、总体描述

题目：给定两个可能有环也可能无环的单链表，头节点head1和head2。请实现一个函数，如果两个链表
相交，请返回相交的第一个节点。如果不相交，返回null

要求：如果两个链表长度之和为N，时间复杂度请达到O(N)，额外空间复杂度请达到O(1)。

思路：先设计一个函数判断链表是否带环，带环则返回第一个入环节点，然后进行分类讨论，无环相交是什么情况，一个带环一个不带环相交是什么情况，两个带环相交是什么情况。

二、细分

1、判断链表带环函数的设计

因为是单链表，所以带环的情况只有一种图形

因为其他的情况，并不符合单链表的特性 

①思路1：哈希表

利用哈希表，遍历链表，每次判断是否contain，并且将该节点插入哈希表，然后往下走

这个方法虽然简单，但是并不符合题目要求，题目要求额外空间复杂度为O(1)

②思路2：快慢指针

利用快慢指针，把链表带环问题转化为追击问题，让两个指针同时指向头节点，fast指针和slow指针，fast指针一次走两步，slow指针一次走一步，如果链表不带环，fast会走到null节点，如果带环，fast指针一定会先进入环，并且在slow指针进入环之后的一段时间追上slow指针，从而解决了判断链表带环的问题，并且空间复杂度为O(1)。

为什么链表带环fast指针一定能追上slow指针以及扩展可以看我的另外一篇文章

https://blog.csdn.net/qq_51654808/article/details/126129856?spm=1001.2014.3001.5501