描述

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

数据范围： n≤10000，1<=结点值<=10000

要求：空间复杂度 O(1)，时间复杂度 O(n)

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

img

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

输入描述：

输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表

返回值描述：

返回链表的环的入口结点即可，我们后台程序会打印这个结点对应的结点值；若没有，则返回对应编程语言的空结点即可。

示例1

输入：

{1,2},{3,4,5}

返回值：

3

说明：

返回环形链表入口结点，我们后台程序会打印该环形链表入口结点对应的结点值，即3

示例2

输入：

{1},{}

返回值：

"null"

说明：

没有环，返回对应编程语言的空结点，后台程序会打印"null"

示例3

输入：

{},{2}

返回值：

2

说明：

环的部分只有一个结点，所以返回该环形链表入口结点，后台程序打印该结点对应的结点值，即2

题解1

如果不考虑空间复杂度，可以使用一个大小为10000的数组a存放各个结点的值，每当遍历到一个节点V的时候，就把a[v-val]++

因为存在换，所以当第一个a[v-val] == 2的时候，即为环的入口结点


/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        vector<int> vt(10000,0);
        while(pHead != nullptr){
            vt[pHead->val]++;
            if(vt[pHead->val] == 2){
                break;
            }
            pHead = pHead->next;
        }
        return pHead;
    }
};

题解2

可以使用快慢指针，快指针fast每次走两步，慢指针slow每次走一步。这样如果有环存在的话，在环中，快慢指针的距离，每移动一次距离就会减一，这样如果它们相遇的话，就一定可以判断链表中有没有环。

那么如何判断环的入口点是在哪里呢？我们假设环前面的节点有a个，环中的节点有b个，慢指针走的长度为S_dis

快指针走的路线为F_dis。当两个指针相遇时，依据题意可以等于以下两个等式

联立可得

可以得出

所以当两个指针相遇的时候，将快指针移到链表头部重新往后走，这次一次走一步。慢指针保持原来的位置，继续向后走，也是一次走一步，当两个指针相遇的时候，即是环的入口处。（这时候快指针刚好走完a = nb的长度到达环的入口处）


/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
  public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        ListNode* slow = pHead;
        ListNode* fast = pHead;
        do {
            slow = slow ->next;
            fast = fast->next->next;
            //如果指向空就说明没有环
            if (slow == nullptr || fast == nullptr) {
                return nullptr;
            }
        } while (slow != fast);
        fast = pHead;
        while (fast != slow) {
            fast = fast->next;
            slow = slow->next;
        }
        return fast;
    }
};