題目說明:給你一個鏈結串列的head,要你求出該鏈結串列是否為cycle
Case 1:
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
Case 2:
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.
Case 3:
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.
解題思路:使用快慢指針(也就是龜兔賽跑)的演算法,快的那個指針一次走兩步,而慢的則一次走一步,若最後快慢指針能夠相遇就代表該鏈結串列有循環(cycle)
附上程式碼以及註解
Java
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
if(head==null || head.next==null){
return false;
//如果該鏈結串列為空(沒有快慢指針可以指向)或是只有一個節點時(缺少快指針)必定回傳false
}
ListNode fast=head.next;//快指針從頭的下一個節點開始
ListNode slow=head;//慢指針從頭開始
while(fast!=slow){
if(fast==null || fast.next==null){
return false;//因為快指針走的較快,所以只要判斷快指針是否為空值即可
}
fast=fast.next.next;//快指針走兩步
slow=slow.next;//慢指針只走一步
}
return true;//有相遇回傳true
}
}
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
if head==None or head.next==None:
return False
#如果該鏈結串列為空(沒有快慢指針可以指向)或是只有一個節點時(缺少快指針)必定回傳false
fast=head.next.next#快指針從頭的之後兩個開始
slow=head.next#慢指針從頭的下一個開始
while fast!=slow:
if fast==None or fast.next==None:
return False
#因為快指針走的較快,所以只要判斷快指針是否為空值即可
fast=fast.next.next#快指針走兩步
slow=slow.next#慢指針只走一步
return True
*fast和slow可以分別從head.next, head開始或從head.next.next, head.next開始皆可