2023-07-29每日一題

一、題目編號

141. 環(huán)形鏈表

二、題目鏈接

點擊跳轉(zhuǎn)到題目位置

三、題目描述

給你一個鏈表的頭節(jié)點 head ，判斷鏈表中是否有環(huán)。

如果鏈表中有某個節(jié)點，可以通過連續(xù)跟蹤 next 指針再次到達，則鏈表中存在環(huán)。 為了表示給定鏈表中的環(huán)，評測系統(tǒng)內(nèi)部使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。注意：pos 不作為參數(shù)進行傳遞 。僅僅是為了標識鏈表的實際情況。

如果鏈表中存在環(huán) ，則返回 true 。 否則，返回 false 。

提示：

• 鏈表中節(jié)點的數(shù)目范圍是 [0, 10⁴]
• -10⁵ <= Node.val <= 10⁵
• pos 為 -1 或者鏈表中的一個 有效索引 。

四、解題代碼

/**
 * 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) {
        int cnt = 0;
        if(head == NULL){
            return false;
        }
        while(head->next != NULL){
            cnt++;
            head = head->next;
            if(cnt > 10001){
                return true;
            }
        }    
    return 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) {
        if(head == NULL || head->next == NULL){
            return false;          
        }
        ListNode *fast = head->next;
        ListNode *slow = head;
        while(fast->next != NULL){
            if(fast == slow){
                return true;
            }
            slow = slow->next;
            fast = fast->next;
            if(fast->next == NULL){
                return false;
            }
            if(fast == slow){
                return true;
            }
            fast = fast->next;
        }
    return false;
    }
};

五、解題思路

(1) 因為我們知道鏈表的最大長度為10⁴,所以我們最直接的做法就是指針嘗試移動10⁴ + 1次，如果能移動這么多次，那么一定會存在環(huán)。這是暴力的解法，在第一段代碼中已經(jīng)給出。

(2) 使用快慢指針來解決問題，快指針每次向前面移動兩下，慢指針每次向前移動一下，如果快指針追上慢指針，那么一定存在環(huán)，如果追不上（到達鏈表最后，那么一定不存在環(huán)）。文章來源地址http://www.zghlxwxcb.cn/news/detail-618551.html

到了這里，關于2023-07-29 LeetCode每日一題（環(huán)形鏈表）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！