本文共 1763 字，大约阅读时间需要 5 分钟。

题目描述:

难度简单699

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

解法一: 快慢指针

这个题非常简单,通常的做法是设置快慢指针,快指针走两步,慢指针走一步而两指针相遇,说明有环

class Solution {public:    bool hasCycle(ListNode *head) {        if (!head || !(head -> next)) return false;        ListNode* slow = head ,* fast = head;        while (fast && fast -> next) {            fast = fast -> next -> next;            slow = slow -> next;            if (fast == slow) {                return true;            }        }        return false;    }};

时空复杂度分析

时间复杂度: 二种情况:

链表没有环时: 为O(N / 2) 也就是快指针(快指针一次循环走二步)指向了NULL ; 去掉常数,也就是O(N);

链表有环时: 最坏情况也就是慢指针走了N个节点+ k 个节点 与块指针相遇,k就是环的长度,为O(N+ K);k与N没有直接的关系,所以也是O(N);

空间复杂度: 使用常量的空间,为O(1);

解法二:使用set容器不能有重复的元素的特性

class Solution {public:    bool hasCycle(ListNode *head) {        set
   
     temp;                while (head){            pair
    
     
      ::iterator,bool> p = temp.insert(head);            if (!p.second) {                return true;            }            head = head -> next;        }        return false;    }};
     
    
   

时空复杂度分析

时间复杂度: 遍历了整个链表节点 为 O(N) N为链表节点的个数;

空间复杂度: 使用了set 容器来存储 链表中的节点,只要碰到环的入口就直接返回true,为O(N);

解法三: 翻转这个链表判断是否有环

ListNode* reverseList(ListNode* head) {	ListNode* prev = NULL,*curr = head; last = NULL;    	while (curr)	{		last = curr->next;		head->next = prev;		prev = curr;		curr = last;	}        return prev;}bool hasCycle(ListNode *head){	ListNode* rev = reverseList(head);	if (head && head->next && rev == head)	{		return true;	}	return false;}

是不是很蒙圈?这是一个国外友人的杰作,链接:https://leetcode.com/problems/linked-list-cycle/discuss/44498/Just-reverse-the-list

我第一次看到的时候我蒙圈了,画张图就明白了了

时空复杂度分析

时空复杂度:

二种情况:

链表没有环时: 翻转了一个链表为O(N);

链表有环时: 翻转时经历了N + (N-k) 个节点 O(N + (N- k));也就是O(N);

空间复杂度:使用了常量的空间,为O(N);

转载地址：http://wdyki.baihongyu.com/