这题让判断链表是否有环，我们可以使用两个指针从链表的头节点开始往后走，一个是慢指针每次只能走一步，一个是快指针，每次只能走两步。
如果链表没有环，如下图所示，最终快指针有可能会指向空，也有可能当快指针指向最后一个节点的话，就没法往后走了。
如果链表有环，无论是快指针还是慢指针都永远不可能指向空，最终它们都会走到环上，因为慢指针每次走 1 步，快指针每次走 2 步，所以在环上的时候每走 1 次，它俩之间的距离就会缩小 1 ，无论它俩相差多远，最终一定会在环上相遇。
所以如果快慢指针相遇了，肯定是有环的，如果快指针指向空了，或者不能再往下走了，说明没有环。
public boolean hasCycle(ListNode head) {
if (head == null)
return false;
ListNode slow = head;// 慢指针每次走一步
ListNode fast = head;// 快指针每次走两步
while (fast != null && fast.next != null) {
slow = slow.next;// 慢指针每次走一步
fast = fast.next.next;// 快指针每次走两步
// 如果相遇，说明有环，直接返回true
if (slow == fast)
return true;
}
return false;// 否则就是没环
}
public:
bool hasCycle(ListNode *head) {
if (head == nullptr)
return false;
ListNode *slow = head;// 慢指针每次走一步
ListNode *fast = head;// 快指针每次走两步
while (fast && fast->next) {
slow = slow->next;// 慢指针每次走一步
fast = fast->next->next;// 快指针每次走两步
// 如果相遇，说明有环，直接返回true
if (slow == fast)
return true;
}
return false;// 否则就是没环
}
除此之外，这题还有另外一种解法，我们可以从头开始，判断每一个节点是否指向它自己，如果指向它自己，说明是有环的，如果没有指向它自己，就让该节点指向它自己，然后继续判断下一个节点。
public boolean hasCycle(ListNode head) {
// 如果head为空，或者他的next指向为空，直接返回false
if (head == null || head.next == null)
return false;
// 如果出现head.next = head表示有环
if (head.next == head)
return true;
ListNode nextNode = head.next;
// 当前节点的next指向他自己，相当于把它删除了
head.next = head;
// 递归，查看下一个节点
return hasCycle(nextNode);
}
public:
bool hasCycle(ListNode *head) {
// 如果head为空，或者他的next指向为空，直接返回false
if (head == nullptr || head->next == nullptr)
return false;
// 如果出现head.next = head表示有环
if (head->next == head)
return true;
ListNode *nextNode = head->next;
// 当前节点的next指向他自己，相当于把它删除了
head->next = head;
// 递归，查看下一个节点
return hasCycle(nextNode);
}
京公网安备 11010502036488号