昨日回顾
昨天我们初步介绍了链表的相关知识，并且通过列举数组和链表的差异，进行了比较学习。之后介绍了链表涉及的相关题型，并举例了第一种链表的第一种删除类题目。那么今天我们就来看看链表的第二类题目：链表的环与交点
环形链表
链表的环是一类在链表中很爱考察的热门题目，今天针对这类题目，带着大家一起学习下。
对于一般的链表，会存在一个头节点，然后根据链表指针一直遍历到链表的结尾即null。但有一种环形链表，这种链表将本该指向null的指针指向了链表自身的某一个节点，构成了一个环形链表。本该是一个非正常的指向，却引出了这类环形链表的问题。
环形链表的结构和构成我们了解了，但如何判断一个链表是否有环呢？让我们来想一个场景。
假设链表的结尾指向的节点是头节点这种特殊场景，那就构成了一个看起来像圆环的链表。我们将这个链表抽象为操场一圈400米的跑道，当前一群运动健儿正在进行10000米的长跑比赛。 大家出于同一起跑点，由于需要跑25圈难免有体育系的运动健将冲在第一名，速度上快最后一名很多。
如果是一个直道，那么他们必然越拉越远，但就因为是环道，所以当第一名快最后一名400米距离时他们相遇了。
那么，我们是不可以将这种现象运用在环形链表上呢？我们构造两个指针，一快一慢，如果他们最终相遇了，代表是环形链表，如果他们没有相遇，则表示链表没有环。所以在做题的时候，我们要开动脑筋，把题目从抽象的概念转化为实际的场景，更有助于解题。
我们知道了要使用快慢指针，但是到底要怎么定义快慢呢？很简单，慢指针一次走一格，快指针一次走两格就行了。当然之前说过机试题一般不会考链表，因为链表都是可以转化为其他数据结构而使用单纯循环解决的，让我们先找一道力扣的上的环形链表入门题看看吧。
141.环形链表
难度：简单
题目：
给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。
进阶：
你能用 O(1)（即，常量）内存解决此问题吗？
提示：
- 链表中节点的数目范围是 [0, 10^4]
- -10^5 <= Node.val <= 10^5
- pos 为 -1 或者链表中的一个 有效索引 。
示例：
分析
先考虑常规场景，设置一个set集合，然后开始while循环，条件为head存在。
每次遍历链表都判断是否存在集合内，存在返回True， 不存在则将当前链表加入到集合中。
最终若while循环结束返回False。
如果考虑O1的空间复杂度，上面的解法不就满足了。需要开始快慢指针的场景。
设置初始指针slow = fast = head,
然后slow = slow.next fast = fast.next.next
即慢的一次走一步，快的一次走两步。如果快的追上了慢的，代码为循环链表。
解题1 集合判断：
Python:
class Solution:
def hasCycle(self, head):
d = set()
while head:
if head in d:
return True
else:
d.add(head)
head = head.next
return False
Java:
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode li = head;
HashSet s = new HashSet();
while (li != null){
if (s.contains(li)){
return true;
}
s.add(li);
li = li.next;
}
return false;
}
}
解题2 快慢指针：
Python:
class Solution:
def hasCycle(self, head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
Java:
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode left = head;
ListNode right = head;
while (right != null && right.next != null) {
left = left.next;
right = right.next.next;
if (left == right) {
return true;
}
}
return false;
}
}
有了这道简单题目的基础，我们就可以进阶的学习书上的22题了。来看看题吧。
剑指offerII022.链表中环的入口节点
https://leetcode-cn.com/problems/c32eOV/
难度：中等
题目
给定一个链表，返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
说明：不允许修改给定的链表。
提示：
- 链表中节点的数目范围在范围 [0, 10 ^ 4] 内
- -10 ^ 5 <= Node.val <= 10 ^ 5
- pos 的值为 -1 或者链表中的一个有效索引
进阶：是否可以使用 O(1) 空间解决此题？
示例
分析
看过了141题的环形链表，相信我们对于判断环形链表已经没有什么问题了，但是这道题要我们求的是环形链表的入口节点，这又该如何解题呢？
之前就说了，遇到链表题画图是一个很好的解决办法。让我们画一个图，通过图形分析这道题吧。
假设快慢指针在W点相遇，此时慢指针走过的路程为x+y，快指针走过的路程为x+y+n(y+z)。
为什么慢指针走过y就必然与快指针相遇，而不是慢指针走过y+m(y+z)呢？
- 首先，由于快指针一定先进入环内，这点毋庸置疑。
- 而且，快指针是慢指针速度的二倍，即慢指针走完一圈，快指针可以走两圈
- 所以不论慢指针入环时，快指针在哪一点，快指针都可以在慢指针未走过一圈时追上慢指针。
而由于快指针走过的节点数是慢指针的二倍，所以得到公式：
(x + y) * 2 = x + y + n (y + z)
两边抵消 x+y，得到 x + y = n (y + z)
由于我们最终要求的是x，所以 x = n (y + z) - y
然而,此时慢指针所走过的路程刚好为y，如果此时有一个指针point从头开始走向环，即x路程
那么，慢指针刚好要走过的就是 n (y + z) - y + y = n (y + z)
即 point 走x的距离到达环的入口的时刻，刚好为slow走过n圈到达入口，两个指针相遇？
得到这个结论，那么题目就迎刃而解了！
解题
Python:
class Solution:
def detectCycle(self, head):
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
point = head
while point!=slow:
point = point.next
slow = slow.next
return point
return None
Java:
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
ListNode point = head;
while (point != slow) {
point = point.next;
slow = slow.next;
}
return point;
}
}
return null;
}
}
环形链表的知识，我们就总结到这里，下来遇到同类型的题目，大家记得思路不清晰的时候多画画图思考下，也许就迎刃而解了。
两个链表相交
除了链表自身成环，还有一种题目是针对两个链表的焦点查找题目。遇到这种题目该如何思考呢？让我们来看看下面这道题目。
剑指offerII023.两个链表的第一个重合节点
https://leetcode-cn.com/problems/3u1WK4/solution/shua-chuan-jian-zhi-offer-day12-lian-bia-m5nz/
难度：简单
题目
给定两个单链表的头节点 headA 和 headB ，请找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
提示：
- listA 中节点数目为 m
- listB 中节点数目为 n
- 0 <= m, n <= 3 * 10 ^ 4
- 1 <= Node.val <= 10 ^ 5
- 0 <= skipA <= m
- 0 <= skipB <= n
- 如果 listA 和 listB 没有交点，intersectVal 为 0
- 如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]
进阶：能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案？
示例
分析
这道题比较容易想到的是，创建一个hash表，然后循环依次A，将A的所有节点添加至Hash表中。
再循环依次B，每次判断B的当前节点是否在hash表中。
代码如下：
class Solution:
def getIntersectionNode(self, headA, headB):
d = {}
while headA:
d[headA] = headA
headA = headA.next
while headB:
if d.get(headB):
return headB
headB = headB.next
return None
这样的思路可以通过，但是题目说了程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
hash表构造了额外的O(n)空间复杂度，那么如何来实现使用O(1)的时间复杂度完成呢？
让我们根据示例1画张草图来分析下：
- 假设相交前A链表的长度为x,B链表的长度为z
- 两个链表相交的点为图中的w
- 相交后共同的长度为y。
- 我们分别创建p1、p2两个指针指向A、B
- 当p1或者p2走到头时，则将指针重新指向另外的一个链表。
- 当p1、p2相等时终止，返回p1或p2就是第一个相交节点。
- 因为p1、p2走过的路程都是x+y+z！
所以我们可以使用上图的方式，通过双指针的解法，来完成这道题目。
解题
Python:
class Solution:
def getIntersectionNode(self, headA, headB):
x, y = headA, headB
while x != y:
x = x.next if x else headB
y = y.next if y else headA
return x
Java:
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode p1 = headA;
ListNode p2 = headB;
while (p1 != p2){
p1 = p1 != null?p1.next:headB;
p2 = p2 != null?p2.next:headA;
}
return p1;
}
}
今天关于链表的环与交点题目，就分享到这里，记得打卡哦！
欢迎关注我的公众号: 清风Python，带你每日学习Python算法刷题的同时，了解更多python小知识。
我的个人博客：https://qingfengpython.cn
网友评论