leetcode 141:Linked List Cycle問題と解答


問題の再現:
  • は、チェーンテーブルを与える、ループが存在するか否かを判定する(できるだけ余分な空間を使用しない)
  • .
    分析の考え方:
      
    1、暴力解法、すなわち、2番目のノードから、それぞれの新しいノードを前のすべてのノードと比較し、サイクルがあるか否かを判断し、時間複雑度をO(N^2)、空間複雑度をO(N)とする
    2、スピードポインタの思想を採用して、つまり2つのポインタでそれぞれチェーンテーブル全体を遍歴して、スピードポインタは毎回1つのノードを前進して、スピードポインタは毎回2つのノードを前進して、もし2つのポインタが出会ったら、それでは循環があると判断します;ループは存在しません.時間的複雑度はO(N),空間的複雑度はO(1)である.
    問題解決:
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     struct ListNode *next;
     * };
     */
    bool hasCycle(struct ListNode *head) {
        
        struct ListNode *fast = head, *slow = head;
        
        while(fast != NULL && fast->next != NULL) {
           
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow)  //if they equal, it has a cycle
                return true;
       }
       
       return false;  //while a pointer is NULL, it doesn't have a cycle
    }