NC4 题解 | #判断链表中是否有环#

题意分析

• 这个题目是NC3的弱化版，这个题目不需要我们求出环的入口结点，只需要我们判断是否存在环就可以。

思路分析

• 所以我们可以按照NC3那题的思路来写。

思路一 哈希处理

• 我们首先将所有的结点存入一个哈希表里面，然后我们需要遍历整个链表，如果存在相同的节点说明存在环，返回true即可。

• 代码如下

  • 需要对整个链表进行遍历，时间复杂度为O(n)
  • 用哈希方法存储整个链表的所有的结点的情况，空间复杂度为O(n)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        map<ListNode*,int> mp; // 定义一个哈希表存储结点指针
        while(head){  // 不断遍历结点
            if(mp[head]){  //如果这个结点出现过
                return true;
            }
            // 如果没有出现过，那么标记为1,表示出现过了
            mp[head]=1;
            head=head->next;
        }
        return false;
    }
};

解法二 数学

• 我们发现，题目特地指明了需要我们使用空间复杂度为O(1)的算法进行求解。所以我们可以接着NC3 中的数学的思路来进行求解。这个代码更加简洁，但是思维含量更高。空间复杂度更低。具体可以看下面的图。
  

• 代码

  • 我们只需要判断是否存在结点，所以当fast指针和slow指针相遇的时候就可以直接停止，时间复杂度为O(直链的长度+环的长度^2)
  • 需要存储整个链表，空间复杂度O(n)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* slow = head; // 定义两个结点指针，fast结点的速度快于slow
        ListNode* fast = head;
        while(fast!=NULL&&fast->next!=NULL){ // 不断让这两个指针移动
            fast=fast->next->next;
            slow=slow->next;
            if(slow==fast){  // 如果存在移动到同一个节点指针，那么说明存在环
                return true;
            }
        }
        return false;
    }
};