/** * 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) return false;        ListNode* fast = head;        ListNode* slow = head;        while (step(fast, 2) && step(slow, 1)) {            if (fast == slow) break;        }        return fast != NULL;    }        bool step(ListNode* &node, int n) {        while (node != NULL && n > 0) {            node = node->next;            n--;        }        return n == 0;    }};

水一发

第二轮：

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

Follow up:

Can you solve it without using extra space?

必做题

1 /** 2  * Definition for singly-linked list. 3  * struct ListNode { 4  *     int val; 5  *     ListNode *next; 6  *     ListNode(int x) : val(x), next(NULL) {} 7  * }; 8  */ 9 class Solution {10 public:11     bool hasCycle(ListNode *head) {12         if (head == NULL) {13             return false;14         }15         ListNode* fast = head->next;16         ListNode* slow = head;17         while (fast != NULL && fast->next != NULL) {18             if (fast == slow) {19                 break;20             }21             slow = slow->next;22             fast = fast->next->next;23         }24         return fast == slow;25     }26 };