Sui Xin's Blog

[剑指Offer]链表中环的入口结点

Posted on In Disqus:

题目描述

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

解题思路

使用快慢指针法。有两种做法：

  1. 方法一（推荐）

    1. 判断是否有环。设置快慢指针，快指针每次走两步，慢指针每次走一步，若快慢指针相遇，则说明该链表包含环。记录相遇结点，停止快慢指针；

    2. 找出环的入口。设置两个指针，一个指针位于链表头，一个指针位于相遇点，同时开始，每次都走1步，相遇时，相遇点即为环的入口。原理如下：

      原理：设从链表头到环的入口长度为$s_a$，从环的入口到相遇点长度为$s_m$，环的长度为$s_c$。则到快慢指针相遇时，$S_{fast}=s_a+ms_c+s_m$，$S_{slow}=s_a+ns_c+s_m$，其中$m$和$n$是非负整数。因为$S_{fast}=2S_{slow}$，则可推出$s_a=(m-2n)s_c-s_m=(m-2n-1)s_c+s_c-s_m$，而$s_c-s_m$为相遇点到环入口剩下的长度，所以相遇点的指针和从头部走的指针总会在环的入口相遇，或走0圈，或1圈……

  2. 方法二
    1. 判断是否有环。设置快慢指针，快指针每次走两步，满指针每次走一步，若快慢指针相遇，则说明该链表包含环。记录相遇结点，停止快慢指针；
    2. 判断环内有多少个结点。设置一个指针指向相遇点，从相遇点开始走，如果再次回到相遇点，则说明已经走了一圈，可得到环内的结点数count；
    3. 找出环的入口。设置两个指针指向链表头，其中一个指针先走count步，然后同时开始走，若两个指针相遇，相遇点即为环的入口。

代码

Python(2.7.3)

方法一（推荐）

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

运行时间：24ms
占用内存：5748k

方法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        if pHead is None or pHead.next is None or pHead.next.next is None:
            return
        fast, slow = pHead, pHead
        while fast.next.next != slow.next:
            fast = fast.next.next
            slow = slow.next
            if fast.next is None or fast.next.next is None:
                return
        circle = slow.next
        count = 1
        while circle.next != slow.next:
            count += 1
            circle = circle.next
        p1, p2 = pHead, pHead
        step = 0
        while step != count:
            step += 1
            p1 = p1.next
        while p1 != p2:
            p1 = p1.next
            p2 = p2.next
        return p1

运行时间：30ms
占用内存：5696k

Related Posts