iT邦幫忙

2022 iThome 鐵人賽

DAY 11
0

題目說明:給你一個鏈結串列的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開始皆可


上一篇
Day 10 Remove Outermost Parentheses
下一篇
Day 12 Valid Palindrome
系列文
從leetcode學習資料結構和演算法31
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言