[LeetCode] 141. Linked List Cycle* 解題思路 (Easy)

這題需要判斷鏈結列表是否是循環的。

LeetCode 題目連結

 

https://leetcode.com/problems/linked-list-cycle/

 

題目

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.

Accept 作法

這題利用 龜兔賽跑 放兩個 Pointer ，烏龜走一步，兔子走兩步最終如果有循環則會對上一樣的節點。時間複雜度為 O(n)。


Runtime: 0 ms
Memory: 39.2 MB

Java 程式碼

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            
            if(fast == slow){
                return true;
            }
        }
        return false;
    }
}

 

更多 LeetCode 相關資源

• Udemy 暢銷 - Master the Coding Interview: Data Structures + Algorithms

 

複習程式面試書籍

除了 LeetCode 練習外，我也入手了這本，題庫來自真正的面試，並非摘自教科書。它們反映出頂尖公司真正會出的題目，你可以藉此做好充分準備。
需要的話可以看看，寫得很仔細。

書名：提升程式設計師的面試力：189道面試題目與解答

• 金石堂實體書資訊
• Hyread 電子書資訊

相關 LeetCode文章一律會放在 程式解題 標籤分類，歡迎持續追蹤。

⇒ 點我看更多程式解題