【剑指Offer】055——链表中环的入口结点 （链表）

题目描述

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

解题思路

一种方法是用 hashmap来存储和查找节点;

file

另一种方法是双指针法。思路：设定两个针指，一个慢指针，一个快指针，快指针的速度是慢指针的二倍，如果有环，他们一定会在环中相遇。两个指针相遇满足：，y点在环中是举例入口结点的举例，假设两个指针在y点相遇，进而得：.这时，将一个指针放在链表得头指针，两个指针都以每次一步得速度往前走，那么两者下一次就会在入口结点相遇。

所以，我们设置两个指针，一个是快指针fast，一个是慢指针slow，fast一次走两步，slow一次走一步，如果单链表有环那么当两个指针相遇时一定在环内。此时将一个指针指到链表头部，另一个不变，二者同时每次向前移一格,当两个指针再次相遇时即为环的入口节点。如果fast走到null则无环。

参考代码

Java

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        // 边界条件
        if(pHead.next == null || pHead.next.next == null)
            return null;
        ListNode slow = pHead.next; // 慢指针
        ListNode fast = pHead.next.next; // 快指针
        while(fast != null){
            //
            if(fast == slow){
                fast = pHead; // 快指针指向头部
                // 再次相遇的时候
                while(fast != slow){
                    fast = fast.next; // 各走一步
                    slow = slow.next; // 各走一步
                }
                return fast;
            }
            slow = slow.next; // 慢指针走一步
            fast = fast.next.next; // 快指针走两步
        }
        return null;
    }
}

Python

# -*- 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.next == None or pHead.next.next == None:
            return None
        slow, fast = pHead.next, pHead.next.next
        while fast:
            if fast == slow:
                fast = pHead
                while fast != slow:
                    fast =fast.next
                    slow = slow.next
                return fast
            slow = slow.next
            fast =fast.next.next
        return None

个人订阅号

image