原创

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

题目描述

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

解题思路

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

file

另一种方法是双指针法。思路:设定两个针指,一个慢指针,一个快指针,快指针的速度是慢指针的二倍,如果有环,他们一定会在环中相遇。两个指针相遇满足:$w+fn+y=2(w+y+sn),f>=2s+1(从后物理意义推的)$,y点在环中是举例入口结点的举例,假设两个指针在y点相遇,进而得:$w=(f-2s)n - 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
正文到此结束
本文目录