Leetcode:linked_list_cycle

Leetcode:linked_list_cycle

一、 題目

給定一個鏈表，確定它是否有一個環，不使用額外的空間？

二、 分析

1. 空鏈表不成環

2. 一個節點自環

3. 一條鏈表完整成環

思路:使用兩個指針，一個每次往前走2步，一個每次往前走1步，兩指針一定會相遇，如果兩個指針相遇，即說明鏈表有環存在，時間復雜度為O(N)，空間復雜度為O(1)。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head==NULL||head->next==NULL) return false;
        if(head->next==head) return true;
        ListNode* node1=head->next;
        ListNode* node2=head->next->next;
        
        while(node1!=NULL&&node2!=NULL){
        	node2=node2->next;
        	if(node2==NULL) break;
        	node2=node2->next;
        	node1=node1->next;
        	if(node1==node2) break;
        }
        return node1==node2;
    }
};



/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head==NULL||head->next==NULL) return false;
        ListNode* node=head->next;
        
        while(node!=NULL&&node->next!=NULL){
        	//一個每次往前走2步，一個每次往前走1步，兩個相遇，
			//即鏈表有環，時間復雜度為O(N)，空間復雜度為O(1)。 
        	if(node==head||node->next==head) return true;
        	node=node->next->next;
        	head=head->next;
        }
        return false;
    }
};



/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        struct ListNode* fast = head;
        struct ListNode* slow = head;
        
        while (fast != NULL && fast->next != NULL) {
            fast = fast->next->next;
            slow = slow->next;
            
            if (fast == slow)
                return true;
        }
        
        return false;
    }
};