題目

判斷給定的鏈表中是否有環(huán)。如果有環(huán)則返回true，否則返回false。

數(shù)據(jù)范圍：鏈表長(zhǎng)度 0≤n≤10000，鏈表中任意節(jié)點(diǎn)的值滿足 ∣val∣<=100000
要求：空間復(fù)雜度 O(1)，時(shí)間復(fù)雜度 O(n)

輸入分為兩部分，第一部分為鏈表，第二部分代表是否有環(huán)，然后將組成的head頭結(jié)點(diǎn)傳入到函數(shù)里面。-1代表無環(huán)，其它的數(shù)字代表有環(huán)，這些參數(shù)解釋僅僅是為了方便讀者自測(cè)調(diào)試。實(shí)際在編程時(shí)讀入的是鏈表的頭節(jié)點(diǎn)。

例如輸入{3,2,0,-4},1時(shí)，對(duì)應(yīng)的鏈表結(jié)構(gòu)如下圖所示：

可以看出環(huán)的入口結(jié)點(diǎn)為從頭結(jié)點(diǎn)開始的第1個(gè)結(jié)點(diǎn)（注：頭結(jié)點(diǎn)為第0個(gè)結(jié)點(diǎn)），所以輸出true。

示例1

輸入：
{3,2,0,-4},1
返回值：
true
說明：
第一部分{3,2,0,-4}代表一個(gè)鏈表，第二部分的1表示，-4到位置1（注：頭結(jié)點(diǎn)為位置0），即-4->2存在一個(gè)鏈接，組成傳入的head為一個(gè)帶環(huán)的鏈表，返回true

示例2

輸入：
{1},-1
返回值：
false
說明：
第一部分{1}代表一個(gè)鏈表，-1代表無環(huán)，組成傳入head為一個(gè)無環(huán)的單鏈表，返回false

示例3

輸入：
{-1,-7,7,-4,19,6,-9,-5,-2,-5},6
返回值：
true

思路1

使用兩個(gè)指針，fast 與 slow。
它們起始都位于鏈表的頭部。隨后，slow 指針每次向后移動(dòng)一個(gè)位置，而fast 指針向后移動(dòng)兩個(gè)位置。如果鏈表中存在環(huán)，則 fast 指針最終將再次與 slow 指針在環(huán)中相遇。

知識(shí)點(diǎn)：雙指針

雙指針指的是在遍歷對(duì)象的過程中，不是普通的使用單個(gè)指針進(jìn)行訪問，而是使用兩個(gè)指針（特殊情況甚至可以多個(gè)），兩個(gè)指針或是同方向訪問兩個(gè)鏈表、或是同方向訪問一個(gè)鏈表（快慢指針）、或是相反方向掃描（對(duì)撞指針），從而達(dá)到我們需要的目的。

解答代碼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) {
        if (head == nullptr) {
            return false;
        }
        // 定義快慢指針
        auto slow = head;
        auto fast = head;
        // 循環(huán)退出條件為快指針先到鏈表尾部
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                // 快慢指針相遇表示有環(huán)
                return true;
            }
        }
        return false;
    }
};

思路2

遍歷鏈表中的每個(gè)節(jié)點(diǎn)，并將它記錄下來；一旦遇到了此前遍歷過的節(jié)點(diǎn)，就可以判定鏈表中存在環(huán)，需借助哈希表（C++中std::unordered_set）。

但這種解法的空間復(fù)雜度為O(N)，其中 N 為鏈表中節(jié)點(diǎn)的數(shù)目。因?yàn)樾枰獙㈡湵碇械拿總€(gè)節(jié)點(diǎn)都保存在哈希表當(dāng)中。

解答代碼2

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
#include <unordered_set>
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == nullptr) {
            return false;
        }
        auto cur = head;
        std::unordered_set<ListNode *> sets;
        while (cur != nullptr) {
            if (sets.find(cur) != sets.end()) {
                // 在unordered_set中找到了，表示有環(huán)
                return true;
            } else
                sets.emplace(cur);
            cur = cur->next;
        }

以上就是C語言刷題判斷鏈表中是否有環(huán)題解的詳細(xì)內(nèi)容，更多關(guān)于C語言判斷鏈表是否有環(huán)的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論