DAY23 Linked List Cycle

第 11 屆 iThome 鐵人賽

DAY 23

自我挑戰組

刷題記錄與人生分享系列第 23 篇

11th鐵人賽 leetcode c javascript

keyhouse12

2019-09-24 08:50:14

1650 瀏覽

分享至

題目:

https://leetcode.com/problems/linked-list-cycle/
給一個連結串列，判斷是否為循環的連結串列。

解題思路:

有2種方式可以做到，第一個是透過2個fast、slow指標，每探訪一次讓slow走一次，fast多走一次，如果是循環連結串列遲早會相遇。第二種方式是透過一個flag紀錄走到哪裡就將其flag變為true，如有循環時則判斷其flag是否為true是的話則回傳true。

C版本:

bool hasCycle(struct ListNode *head) {
    struct ListNode *fast = head;
    struct ListNode *slow = head;
    while(fast != NULL && fast -> next != NULL)
    {
        slow = slow -> next;
        fast = fast -> next -> next;
        if(slow == fast)
            return true;
    }
    return false;
}

Javascript版本:

var hasCycle = function(head) {
    if(head == null || head.next == null){
        return false; 
    }
    var node = head;
    while(node != null ){
        if(node.flag){
            return true;
        }    
        node.flag = true;   
        node = node.next;
    }
    return false;
};