leetcode刷題03--鏈表求環(huán)--T141,142
題目:
image.png
T141和T142的區(qū)別在于:前者不用返回環(huán)起始節(jié)點(diǎn),后者需要
思路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) {
//創(chuàng)建set集合
std::set<ListNode*> node_list;
//將鏈表中的集合一個(gè)一個(gè)放入set中
while(head){
//先進(jìn)行查找
if(node_list.find(head) != node_list.end()){
return head;
}
node_list.insert(head);
head = head->next;
}
return NULL;
}
};
思路二:
思路一因?yàn)橛昧藄et集合,算比較賴皮的做法了,而且時(shí)間復(fù)雜度較高,下面介紹的思路二時(shí)間復(fù)雜度會(huì)少一些
這里運(yùn)用了快慢指針的概念:
給出解釋:
相當(dāng)于兩個(gè)人跑步,一個(gè)人快,一個(gè)人慢,如果是環(huán)形跑道,那么快的那個(gè)人
肯定可以追上慢的那個(gè)人
這種快慢指針也是如此,一個(gè)指針步長(zhǎng)為2一個(gè)為1,如果兩者相遇,則鏈表必定有環(huán)
如圖:
image.png
當(dāng)然,還有一個(gè)問(wèn)題,如何確定環(huán)的起點(diǎn)?
這里運(yùn)用了幾何關(guān)系,具體解釋可以看圖
大致意思是:從head起點(diǎn)到環(huán)起點(diǎn)的距離和兩個(gè)快慢指針相遇點(diǎn)到環(huán)起點(diǎn)的距離相等.
image.png
好了,思路基本上沒(méi)有問(wèn)題了,上代碼:
/**
* 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開(kāi)始
ListNode *slow = head;
ListNode *fast = head;
//遍歷
while(fast){
//slow前進(jìn)一步
//fast前進(jìn)兩步
slow = slow->next;
//不能直接往下兩步,先一步,然后判空后再一步
fast = fast->next;
if(!fast){
//為空直接返回
return NULL;
}
fast = fast->next;
//對(duì)比,要相等且不為空
if(fast == slow){
//存在環(huán)!
break;
}
}
//存在環(huán)才會(huì)進(jìn)入此判斷內(nèi)
if(fast == slow){
//讓head和fast各一步一步向下指,相遇點(diǎn)就是環(huán)的起始點(diǎn)
while(head != fast){
head = head->next;
fast = fast->next;
}
return head;
}
return NULL;
}
};
總結(jié):
今天的代碼都是自己看了思路之后,直接想的,我想以后也要這樣,不能依賴別人的代碼,一定要自己親自實(shí)現(xiàn),否則那些思想和提高始終不會(huì)是自己的.
大概刷題流程:
看ppt題目介紹->先自己想如果有思路就嘗試
如果沒(méi)有思路就看ppt的思路,然后自己嘗試實(shí)現(xiàn)代碼,盡量實(shí)現(xiàn),嘗試提交
最后進(jìn)行對(duì)比和查看思路差異
加油,天道酬勤,功不唐捐!
