當前位置:網站首頁>判斷鏈錶“卷”不“卷”?【141. 環形鏈錶】(Leetcode 熱題 Hot100)

判斷鏈錶“卷”不“卷”?【141. 環形鏈錶】(Leetcode 熱題 Hot100)

2022-01-27 10:44:47 南七丶

️LeetCode每日一題️



題目描述
給你一個鏈錶的頭節點 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

隨機推薦