题意分析

  • 这个题目给我们一个经过特殊处理的链表，这个链表分为两段，每一段包含一个链表的非环的部分和成环的部分。大多数人可能一开始看样例的时候会感觉不是很理解。其实你就只要知道它给你一个链表，这个链表中如果成环的话就说明这个链表里面存在相同的结点。也就是转化为问你给出一个链表，需要你判断这个链表里面是否存在相同的结点。返回这个相同的结点就行了。如果不存在环，那么就返回一个空指针。
  • 样例可以结合这个图进行理解

图片说明

  • 前置知识，这个题目我们可以使用哈希算法进行处理，我们可以一边遍历整个链表，一边将所有的结点进行哈希处理。对于C++，有一个实现好的STL容器就是map，我们第一种写法就是利用这个来实现的。

思路分析

解法一 哈希

  • 我们知道，既然要寻找两个相同的结点，那么我们就可以将这些结点存入哈希函数里面，我们遍历整个链表，如果当前这个结点已经不是初始的值，那么我们就可以判断这个就是一个环的入口。
  • 代码如下
    • 最坏的情况就是遍历整个链表，所以时间复杂度为O(n），
    • 用哈希方法存储整个链表的所有的结点，空间复杂度为O(n) 
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        map<ListNode*,int> mp; // STL中的map进行哈希，初始的时候所有的哈希值都是0
        while(pHead){  //遍历整个链表
            if(mp[pHead]){  //如果这个结点指针的哈希值不是0，那么说明之前出现过
                return pHead;
            }
            // 走到这一步说明这个是第一次出现的，标记这个哈希值为1
            mp[pHead]=1; 
            pHead=pHead->next;
        }
        // 如果不存在的情况记得要返回一个空指针
        return NULL;
    }
};

解法二 数学法

  • 第二种方法是题解区看到的觉得比较新奇的解法。这种解法需要我们进行结合几何图形进行理解。首先，我们来看一下下面的图。

图片说明

  • 代码如下
    • 假设在环上slow指针只能靠近fast指针一个位置，那么时间复杂度就是O（不成环的长度+成环的长度^2)
    • 由于我们存储整个链表的所有的结点，所有空间复杂度为O(n) 
/*
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;
        while(fast!=NULL&&fast->next!=NULL){
            fast=fast->next->next; //fast指针走两步
            slow=slow->next;  // slow指针走一步
            if(slow==fast){  //找到了相遇点
                while(pHead!=slow){  //不断往前走
                    pHead=pHead->next;
                    slow=slow->next;
                }
                return pHead;
            }
        }
        return NULL;
    }
};