一道编程题——判断链表是否有环

题目描述

判断给定的一个链表中是否有环。如果有环则返回true，否则返回false。需要给出空间复杂度为O(1)的解法。

题目分析

这一题困难之处在于解法的空间复杂度需要满足O(1)。

上图就是链表存在环的情况，画这个图的目的是表明，有环就2种情况，一是开始不是环，后面部分组成环。二是整个链表就是一个循环单链表。不会存在开始有环而链表尾不属于环的情况。

而单链表有环的本质是链表中存在链表节点出现了2次。

最简单的解法，是遍历链表，将链表的节点元素加入到一个哈希表中，哈希表发生冲突则表明有2个节点重复，即为有环。对于python来说，可以把链表元素加入到集合（ set ）中，判断是否重复出现。

当然，这种解法的空间复杂度为 O(n)，不满足题目要求。

快慢指针

在来链表操作中，如果需要满足空间复杂度为 O（1） ，则常用到快慢指针，比如一个指针快而一个指针慢，或者一个指针先走一个后走。

本地设置2个指针，一个慢指针每次遍历一个节点，另外一个快指针每次遍历2个节点，如果存在环，则快指针先进入环，等到慢指针进入环后，快指针将与慢指针相遇。

python

# 思路比较简单，不再注释，详细见上述介绍
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self , head ):
        # write code here
        if not head:
            return False
        slow_p = fast_p = head
        while(fast_p and fast_p.next):
            fast_p = fast_p.next.next
            slow_p = slow_p.next
            if fast_p == slow_p:
                return True
        return False

c++

/**
 * 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) {
        if(!head) {
            return false;
        }
        ListNode* slow_p = head;
        ListNode* fast_p = head;
        while(fast_p && fast_p->next){
            fast_p = fast_p->next->next;
            slow_p = slow_p->next;
            if(fast_p == slow_p){
                return true;
            }
        }
        return false;
    }
};