leetcode刷题03--链表求环--T141,142
题目:
image.png
T141和T142的区别在于:前者不用返回环起始节点,后者需要
思路1:
用set求解
如图:
image.png
思路很容易理解
直接上代码了
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
//创建set集合
std::set<ListNode*> node_list;
//将链表中的集合一个一个放入set中
while(head){
//先进行查找
if(node_list.find(head) != node_list.end()){
return head;
}
node_list.insert(head);
head = head->next;
}
return NULL;
}
};
思路二:
思路一因为用了set集合,算比较赖皮的做法了,而且时间复杂度较高,下面介绍的思路二时间复杂度会少一些
这里运用了快慢指针的概念:
给出解释:
相当于两个人跑步,一个人快,一个人慢,如果是环形跑道,那么快的那个人
肯定可以追上慢的那个人
这种快慢指针也是如此,一个指针步长为2一个为1,如果两者相遇,则链表必定有环
如图:
image.png
当然,还有一个问题,如何确定环的起点?
这里运用了几何关系,具体解释可以看图
大致意思是:从head起点到环起点的距离和两个快慢指针相遇点到环起点的距离相等.
好了,思路基本上没有问题了,上代码:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
//定义快慢指针,都从head开始
ListNode *slow = head;
ListNode *fast = head;
//遍历
while(fast){
//slow前进一步
//fast前进两步
slow = slow->next;
//不能直接往下两步,先一步,然后判空后再一步
fast = fast->next;
if(!fast){
//为空直接返回
return NULL;
}
fast = fast->next;
//对比,要相等且不为空
if(fast == slow){
//存在环!
break;
}
}
//存在环才会进入此判断内
if(fast == slow){
//让head和fast各一步一步向下指,相遇点就是环的起始点
while(head != fast){
head = head->next;
fast = fast->next;
}
return head;
}
return NULL;
}
};
总结:
今天的代码都是自己看了思路之后,直接想的,我想以后也要这样,不能依赖别人的代码,一定要自己亲自实现,否则那些思想和提高始终不会是自己的.
大概刷题流程:
看ppt题目介绍->先自己想如果有思路就尝试
如果没有思路就看ppt的思路,然后自己尝试实现代码,尽量实现,尝试提交
最后进行对比和查看思路差异
加油,天道酬勤,功不唐捐!
网友评论