剑指offer 链表中环的入口结点

Posted on |

链表中环的入口结点

题目

142.环形链表II
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

方法：快慢指针

参考资料，请看图
快慢指针，快指针走两步，慢指针走一步。链表的起点是A，环的入口是B，相遇点是C。顺时针

  • A到B的距离为X
  • B到C的距离为Z
  • C到B的距离为Y
  • 环的长度为L

即。这就意味这，slow和fast相遇后，slow在相遇点C。此时head和slow分别从A和C出发，步长为1，当slow在C点出发多走(n-1)圈（距离(n-1)L+Y)，会与在起点A出发的head相遇，此时相遇点就是换的入口点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        slow=fast=pHead
        while fast and fast.next:
            fast=fast.next.next
            slow=slow.next
            if fast==slow:
                while slow!=pHead:
                    pHead=pHead.next
                    slow=slow.next
                return slow