當前位置:網站首頁>判斷鏈錶“卷”不“卷”?【141. 環形鏈錶】(Leetcode 熱題 Hot100)
判斷鏈錶“卷”不“卷”?【141. 環形鏈錶】(Leetcode 熱題 Hot100)
2022-01-27 10:44:47 【南七丶】
️LeetCode每日一題️
- 博客主頁:南七的博客主頁
- 期待得到大家的點贊收藏留言和關注
- 持續刷題,每日一題 05
- Leetcode 熱題 Hot100
- 博主水平有限,如果發現有不對的地方,希望大佬們指正!
- 放弃很容易,但堅持一定很酷,人生一次,怎願甘拜下風!
- 來源:Leetcode 熱題 Hot100 141. 環形鏈錶
- 系列文章持續更新中…
1.擋住眾人的兩數之和…
2.趁室友吃雞,刷一道回文鏈錶
3.我連兩個數相加都不會(撓頭ing)(Leetcode 熱題 Hot100)
4.終於秒殺了一題【删除鏈錶的倒數第 N 個結點】(Leetcode 熱題 Hot100)
題目描述
給你一個鏈錶的頭節點 head ,判斷鏈錶中是否有環。
如果鏈錶中有某個節點,可以通過連續跟踪 next 指針再次到達,則鏈錶中存在環。 為了錶示給定鏈錶中的環,評測系統內部使用整數 pos 來錶示鏈錶尾連接到鏈錶中的比特置(索引從 0 開始)。如果 pos 是 -1,則在該鏈錶中沒有環。注意:pos 不作為參數進行傳遞,僅僅是為了標識鏈錶的實際情况。
如果鏈錶中存在環,則返回 true 。 否則,返回 false 。
示例 1:
輸入:head = [3,2,0,-4], pos = 1
輸出:true
解釋:鏈錶中有一個環,其尾部連接到第二個節點。
示例 2:
輸入:head = [1,2], pos = 0
輸出:true
解釋:鏈錶中有一個環,其尾部連接到第一個節點。
示例 3:
輸入:head = [1], pos = -1
輸出:false
解釋:鏈錶中沒有環。
博主題解1️⃣:
剛拿到題目還是有點懵的,沒看懂題目的pos是什麼意思。之後才反應過來,pos標明的是鏈錶尾所指向前面結點的索引號。該題要求判斷鏈錶是否成環,該鏈錶是單向鏈錶,那麼應該就會想到,如果鏈錶成環的話,其中的某些結點一定是會被重複訪問的。那麼第一個想到的就是,我們只要知道,該鏈錶是否被訪問過就可以了。可惜不是自定義的鏈錶結構,我第一個想到的是給每一個結點添加一個狀態,被訪問過的結點直接更改其狀態就可以了。可是,鏈錶結構是規定死的,無法更改。這就突然讓我想到使用哈希錶的辦法。對於每一個訪問過的結點,我們只需要將其添加到哈希錶中即可。那麼Set集合就可以很好的幫助我們,set集合是不允許出現重複元素的,當我們想要向錶中添加已經存在的元素時,就會返回false,那麼這個就是我們的關鍵判斷條件了。
public class Solution {
public boolean hasCycle(ListNode head) {
Set<ListNode> set = new HashSet<>();
ListNode cur = head;
while(cur != null){
//如果當前結點已經遍曆過了,就添加失敗,返回false
if(!set.add(cur)){
return true;
}
//指針後移
cur = cur.next;
}
return false;
}
}
博主題解2️⃣:
還有一種辦法–快慢指針。我們給定兩個指針,讓他們都指向頭結點,快指針每次向後遍曆兩個結點,慢指針每次向後遍曆一個結點。試想一下,如果鏈錶成環,那麼快指針很快又會和慢指針相遇。這就像我們在一個操場上跑步,你們同時出發,可能下次再見到他的時候,他已經甩你一圈了。所以,我們只需要判斷,兩個指針是否相遇,如果相遇,就說明鏈錶成環。如果fast指針為空了,就說明鏈錶不成環。
public class Solution {
public boolean hasCycle(ListNode head) {
if(head == null){
return false;
}
ListNode fast = head;
ListNode slow = head;
//這裏只需要判斷快指針就行了
//博主一開始還傻乎乎的在那判斷slow != null,快指針為null,自然就不需要判斷慢指針了
while(fast != null&&fast.next != null){
//快指針每次向後遍曆兩個結點
fast = fast.next.next;
//慢指針每次向後遍曆一個結點
slow = slow.next;
//如果二者相遇,說明鏈錶成環,返回true
if(fast == slow)
return true;
}
return false;
}
}
期待得到大家的點贊收藏留言和關注
版權聲明
本文為[南七丶]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/01/202201271044467333.html
邊欄推薦
猜你喜歡
隨機推薦
- win7系統上將電腦變為熱點的辦法
- Jedis連接阿裏雲redis
- 線程的生命周期,真的沒那麼簡單
- 【行研資料】2021年中國AI中臺賦能城市空間管理白皮書——附下載
- emplace_back 和 push_back 的區別
- 藍橋杯第三講--二分【習題】
- 地址的地址?
- Qt給靜態屏保加上粒子特效
- 圖的著色問題
- cesium導入旋轉動畫
- QGC雜記
- 面試面到自閉,職場反思,原來是我沒有掌握其中精髓
- CISP——關於網絡安全法(分享筆記)
- 通過ReentrantLock源碼看AQS源碼實現
- Js基礎_作用域
- Endnote使用方法——檢查參考文獻
- 記錄在appA裏面打開appB進行登錄,再次點擊桌面圖標appB避免再次重新啟動程序的解决辦法
- 自建Kubernetes的LoadBalancer類型服務方案-MetalLB
- JS中的forEach()和map()方法介紹
- 【ISO15765_UDS&OBD診斷】-02-Network layer網絡層介紹
- 百度BML-飛槳服務器以及Jetson nano部署實戰案例(下)
- 適合10歲小孩投保的保險產品都有什麼啊?少兒險可以買哪些險種?
- 北京大學2022年對元宇宙的全球研究報告
- 網上期貨開戶安全麼?期貨開戶准備什麼資料?
- 查看多臺jps的脚本
- #全網寒假最火特輯# 【第一章】 C語言之牛客網刷題筆記 【點進來保證讓知識充實你一整個寒假】
- Material Design 3 全新的進階版本UI庫
- 雲演 CTF Web題型 lfi 文件包含
- 【leectode 2022.1.22】批量處理任務
- IC驗證中的force/release 學習整理(4)後門訪問機制成與敗(續)
- Leetcode 算法面試沖刺 實戰 五(數組與循環)(十二)
- 數學建模-模糊綜合評價法(評價模型)
- Vulnhub靶機recon: 1滲透
- DWR异常:org.xml.sax.SAXException
- ZZULIOJ 1173: 密碼解密(指針專題)
- 掃雷初階版
- DCGAN 源碼解析
- [渝粵教育] 東南大學 工程熱力學 參考 資料
- Go 自定義日期時間格式解析解决方案 - 解决 `parsing time xx as xx: cannot parse xx as xx` 錯誤
- Redis 是如何處理命令的(客戶端)