LeetCode Linked List Cycle 解答程序

Linked List Cycle

Given a linked list, determine if it has a cycle in it.

Follow up:

Can you solve it without using extra space?

错误解法。因为Cycle可能出现在Link的中间的，所以需要检查其中间Nodes。

bool hasCycle(ListNode *head) {  
        // IMPORTANT: Please reset any member data you declared, as  
        // the same Solution instance will be reused for each test case.  
        if(head == NULL)  
            return false;  
  
        ListNode *cur = head;  
        while(cur != NULL)  
        {  
            cur = cur->next;  
            if(cur == head)  
                return true;  
        }  
        return false;  
    }

正确解法：

class Solution {  
public:  
  
    bool find(ListNode *head, ListNode *testpNode)  
    {  
        ListNode *p = head;  
        while (p != testpNode->next)  
        {  
            if(p == testpNode)  
                return false;  
            p = p->next;  
        }  
        return true;  
    }  
  
  
    bool hasCycle(ListNode *head) {  
        // IMPORTANT: Please reset any member data you declared, as  
        // the same Solution instance will be reused for each test case.  
        if(head == NULL)  
            return false;  
  
        ListNode *cur = head;  
        while(cur != NULL)  
        {  
            if(find(head, cur))  
                return true;  
            cur = cur->next;  
        }  
        return false;  
    }  
};

补充：软件开发 , C++ ,