快捷導航

C語言刷題判斷鏈表中是否有環(huán)題解

更新時間：2023年07月26日 10:42:38 作者：吳尼瑪

這篇文章主要為大家介紹了C語言刷題判斷鏈表中是否有環(huán)題解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪

題目

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

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

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

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

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

示例1

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

示例2

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

示例3

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

思路1

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

知識點：雙指針

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

解答代碼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

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

但這種解法的空間復雜度為O(N)，其中 N 為鏈表中節(jié)點的數(shù)目。因為需要將鏈表中的每個節(jié)點都保存在哈希表當中。

解答代碼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)題解的詳細內(nèi)容，更多關(guān)于C語言判斷鏈表是否有環(huán)的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: