题目:
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
给出一个链表,判断他是否是一个循环链表(不开辟多余的内存空间进行解决,意思是在利用链表本身的特性进行解决问题)分析:
我们可以开辟两个指针节点,一个快的节点,每次跳跃两步,一个慢的节点,每次跳跃一步,然后进行一个while循环,如果两个指针节点相同出现相同的情况下,那么说明是存在环的代码:
bool hasCycle(ListNode *head) {
if (head == NULL || head->next == NULL) {
return false;
}
ListNode *fastNode = head;
ListNode *slowNode = head;
while (fastNode->next != NULL && fastNode->next->next != NULL) { // 由于fastNode比slowNode增长快,所以只需要判断fastNode,同时对于fastNode需要判断后两位,所以第一位的判断也是必须的,不然会出现Runtime Error
fastNode = fastNode->next->next; // 每次往后移动两步
slowNode = slowNode->next; // 每次往后移动一步
if (fastNode == slowNode) {
return true;
}
}
return false;
}