C++實(shí)現(xiàn)LeetCode(141.單鏈表中的環(huán))
[LeetCode] 141. Linked List Cycle 單鏈表中的環(huán)
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.
Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.
Example 2:
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.
Example 3:
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.
Follow up:
Can you solve it using O(1) (i.e. constant) memory?
這道題是快慢指針的經(jīng)典應(yīng)用。只需要設(shè)兩個(gè)指針，一個(gè)每次走一步的慢指針和一個(gè)每次走兩步的快指針，如果鏈表里有環(huán)的話，兩個(gè)指針最終肯定會(huì)相遇。實(shí)在是太巧妙了，要是我肯定想不出來。代碼如下：
C++ 解法：
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}
};
Java 解法：
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}
}
Github 同步地址：
https://github.com/grandyang/leetcode/issues/141
類似題目：
參考資料：
https://leetcode.com/problems/linked-list-cycle/
https://leetcode.com/problems/linked-list-cycle/discuss/44489/O(1)-Space-Solution
到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(141.單鏈表中的環(huán))的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)單鏈表中的環(huán)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
本文給大家介紹C++ 中try finally關(guān)鍵字的相關(guān)知識(shí)，非常不錯(cuò)，本文介紹的非常詳細(xì)，具有參考借鑒價(jià)值，感興趣的朋友一起學(xué)習(xí)吧2016-05-05
OpenCV實(shí)現(xiàn)特征檢測(cè)和特征匹配方法匯總
一幅圖像中總存在著其獨(dú)特的像素點(diǎn)，這些點(diǎn)我們可以認(rèn)為就是這幅圖像的特征，成為特征點(diǎn)，本文主要介紹了OpenCV實(shí)現(xiàn)特征檢測(cè)和特征匹配方法，感興趣的可以了解一下2021-08-08
C++簡(jiǎn)明圖解分析靜態(tài)成員與單例設(shè)計(jì)模式
與靜態(tài)數(shù)據(jù)成員不同，靜態(tài)成員函數(shù)的作用不是為了對(duì)象之間的溝通，而是為了能處理靜態(tài)數(shù)據(jù)成員，靜態(tài)成員函數(shù)沒有this指針。既然它沒有指向某一對(duì)象，也就無法對(duì)一個(gè)對(duì)象中的非靜態(tài)成員進(jìn)行默認(rèn)訪問2022-06-06
本文主要介紹了VS2017中配置QT5.12.0的圖文教程，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-06-06
nique()是C++標(biāo)準(zhǔn)庫函數(shù)里面的函數(shù)，下面這篇文章主要給大家介紹了關(guān)于C++中unique函數(shù)用法的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，需要的朋友可以參考借鑒，下面來一起看看吧2019-02-02
一維指針其實(shí)就相當(dāng)于一維數(shù)組，不用去看書上所說的數(shù)組在內(nèi)存中的首地址這些晦澀的話，以此類推 二維指針就相當(dāng)于二維數(shù)組，新手對(duì)一維數(shù)組的開辟與釋放比較容易熟悉2013-09-09
C預(yù)處理器不是編譯器的組成部分，但是它是編譯過程中一個(gè)單獨(dú)的步驟。簡(jiǎn)言之，C預(yù)處理器只不過是一個(gè)文本替換工具而已，它們會(huì)指示編譯器在實(shí)際編譯之前完成所需的預(yù)處理。我們將把C預(yù)處理器（C Preprocessor）簡(jiǎn)寫為CPP2022-12-12
本文主要講解C語言 數(shù)據(jù)類型,這里整理了詳細(xì)的數(shù)據(jù)類型的資料,希望能幫助剛剛開始學(xué)習(xí)C語言的同學(xué)2016-08-08
這篇文章主要介紹了C語言中操作密碼文件的一些函數(shù)總結(jié),包括setpwent()函數(shù)和getpwent()函數(shù)以及endpwent()函數(shù),需要的朋友可以參考下2015-08-08
這篇文章主要為大家詳細(xì)介紹了如何使用C語言實(shí)現(xiàn)從avi視頻中提取圖片,文中的示例代碼簡(jiǎn)潔易懂,具有一定的借鑒價(jià)值,有需要的小伙伴可以參考下2023-10-10