[LeetCode] 141. Linked List Cycle

链接：141. Linked List Cycle

描述：判断一个单链表，判断其是否有环。

要求：最好不用分配额外的空间。

思路：“有环”的意思是指链表的最后一个结点的下一节点域又指向了当前链表其中的一个结点。这样一来，遍历链表的时候就会进入死循环。典型的两个指针问题（本题也作跑道问题），一快一慢，如果存在环，快者一定会在某个时刻与慢者相遇。

代码：

#include "stdafx.h"

// https://leetcode.com/problems/linked-list-cycle/

using namespace std;

struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution
{
public:
    bool hasCycle(ListNode* head)
    {
        ListNode* p = head;
        ListNode* q = head;

        while(q && q->next) {
            p = p->next;
            q = q->next->next;

            if(p == q)
                return true;
        }

        return false;
    }
};

int main_141()
{
    ListNode l11(1), l12(5), l13(6);

    l11.next = &l12;
    l12.next = &l13;
    l13.next = &l11;

    Solution so;
    cout << boolalpha << so.hasCycle(&l11) << endl;

    return 0;
}