链表中环的入口结点

• fast：2步；slow：1步；

题目描述

给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。

例如，输入{1,2},{3,4,5}时，对应的环形链表如下图所示：

可以看到环的入口结点的结点值为3，所以返回结点值为3的结点。

C++实现

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
#include <unordered_set>
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        // hash-map
        ListNode *fast = pHead;
        ListNode *slow = pHead;
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) {
                break;
            }
        }
        if (!fast || !fast->next) {
            return nullptr;
        }

        fast = pHead;
        while (fast != slow) {
            fast = fast->next;
            slow = slow->next;
        }

        return slow;
    }
};

golang实现

package main

func EntryNodeOfLoop(pHead *ListNode) *ListNode{
    slow := hasCycle(pHead);
    if slow == nil {
        return nil
    }

    fast := pHead
    for fast != slow {
        fast = fast.Next
        slow = slow.Next
    }

    return slow
}

func hasCycle(pHead *ListNode) *ListNode{
    for fast,slow := pHead,pHead; fast != nil && fast.Next != nil; {
        fast = fast.Next.Next
        slow = slow.Next
        if fast == slow {
            return slow
        }
    }
    return nil
}