【小白爬Leetcode141】1.4环形链表 Linked List Cycle
【小白爬Leetcode】1.4环形链表 Linked List Cycle
Leetcode 141
题目
Description
Given a linked list, determine if it has a cycle in it.
To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.
Follow up:
Can you solve it using O(1) (i.e. constant) memory?
中文描述
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
思路一 暴力解法，空间复杂度O(n)
就是用set记录指针，如果遍历的指针在set里有过了，那肯定是循环了，直接返回这个指针；
如果遇到NULL，肯定是个非循环链表，直接返回跳出循环返回False。
/**
* 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) {
std::set<ListNode*>node_set;
while(head)
{
if(node_set.find(head)!=node_set.end())
{
return true;
}
node_set.insert(head);
head = head->next;
}
return false;
}
};
思路二 快慢指针赛跑
受到交叉链表思路的影响，其实一开始我也想过两个指针互相追，但是我不知道如何能让两个相遇。看到这个思路，真的感到了降智打击。
**原理很简单：**在一条有限长的环形跑道上，无论跑道有多长，慢的人总能被快的人从身后追上。
第一次尝试，用力过猛：
每一次while循环，慢指针往前走一个，快指针每一步加速一步，越来越快，这样肯定会追上。
/**
* 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* fast = head;
int fast_step = 2;
ListNode* slow = head;
while(fast && slow)
{
slow = slow->next;
for(int i=0;i<fast_step;i++)
{
fast = fast->next;
if(fast == NULL)
{return false;}
}
if(fast==slow)
{
return true;
}
fast_step++;
}
return false;
}
};
结果依旧很惨淡，一定有更简单的方法？
来到评论区，发现问题出在快指针每一步加速一步。让子弹飞里有句话：步子大了，容易扯着egg，每一个while循环都让fast_step加速很容易让快慢指针一次次擦肩而过。让fast_step==2，slow_step每次为1，那么可以确保第一次二者就能相遇，具体的数学原理如下：
图片来源：leetcode中国站
这里直接用leetcode原话。另外注意这里 h(mod C) 的意思是，h是经过对C取余运算后的值。
“因此，如果列表是有环的，快指针和慢指针最后会同时指向同一个节点，因此被称为 相遇 。”
综上，直接删掉源代码里的fast_step++;即可。
思路三 这也太贱了hhh
秀儿一：
好嘛，原链表全毁了
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
while head:
if head.val == 'bjfuvth':
return True
else:
head.val = 'bjfuvth'
head = head.next
return False
秀儿二：
public class Solution {
public boolean hasCycle(ListNode head) {
int count=8029;
while(head!=null&&count>0){
head=head.next;
count--;
}
if(head==null)
return false;
return true;
}
}
秀儿三：
这位老哥把链表撕得稀碎，但是比我聪明得多。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
//新建END节点，将遍历过的节点指向END，如果==END就是有环
class Solution {
public:
bool hasCycle(ListNode *head) {
if(!head) return false;
ListNode * END =new ListNode(0);
ListNode* pre;
while(head){
if(head==END) return true;
pre=head;
head=head->next;
pre->next=END;
}
return false;
}
};