链表06-环形链表

Posted on

题: 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

环形链表

本道题主要由两个考点组成

  • 判断链表中知否含环
  • 找到环的入口

一、是否含环的判断

有环的判断非常简单 ，就是看快慢指针最后会不会在环内相遇

我们让fast指针每次走两步 slow每次走一步 ，那么当slow fast都进入环内时，就变成fast追赶slow，并且两者的步伐每次差一步，所以fast最后一定可以撞上slow指针。

但是如果fast每次走三步 就可能出现fast直接超过slow，不相遇的情况

判断有无环的代码如下

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def hasCycle(self, head):
        slow=head
        fast=head
        
        while fast and fast.next:
            slow=slow.next
            fast=fast.next.next
            
            if fast == slow:
                return True
         return False

二、找到环的起点

判断环的起点后，如何才能找到环的起点呢 ，说实话，不是那么好理解，画图和列公式来辅助

环图

如图，我们把整个链表的路径分成x, y ,z三段，那么我们就可以得到

slow指针的总路径：x + y

fast指针的总路径：x + n(y+z) + y （其中n为快指针绕的圈数，n>=1）

抓住快指针走过的路径是慢指针的两倍：

2(x + y)=x + n(y + z) + y

化简，变化后的结果是

x = (n - 1) (y + z) + z

这个公式说明，此时如果从起点和相遇点同时放一个指针，保持同样的速度一起走，那么他们相遇的时候，相遇点一定就是环的入口。至于n的取值根本无所谓，取多大无非就是环内的指针多转几圈，反正最后的一定要在环口相遇。

实在不好理解就死记吧 相遇点和起点分别放指针，相遇便是环起点

完整题解代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def detectCycle(self, head):
        slow =head
        fast =head
        flag=0 
        while fast and fast.next:   # fast.next and fast.next.next是错误写法 
            slow=slow.next
            fast=fast.next.next
            
            if slow == fast:
                slow=head
                while slow != fast:
                    slow=slow.next
                    fast=fast.next
                return fast           
        return None