链表入门练习：判断是否有环的两种解法

本文主要是介绍链表入门练习：判断是否有环的两种解法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

NC4 判断链表中是否有环

给出一个链表，判断其中是否有环。

如上图示，如果链表中有环，则意味着尾结点的 next 指针指向了某个结点。

方法一：双指针

当一个链表有环时，快慢指针必然会进入到环中。想象一下在操场跑步的场景，只要一直跑下去，快的总会追上慢的(也就是套了一圈)。

当两个指针都进入环后，每轮移动使得慢指针到快指针的距离增加一，同时快指针到慢指针的距离也减少一，只要一直移动下去，快指针总会追上慢指针。
快慢指针在环上追及

不难得出结论，如果一个链表存在环，那么快慢指针必然会相遇。实现代码如下：

class Solution {
public:bool hasCycle(ListNode *head) {ListNode *fast = head, *slow = head;do {if (fast != nullptr && fast->next != nullptr) {fast = fast->next->next;slow = slow->next;} else {return false;}} while (fast != slow);return true;}
};

方法二：修改 next 指针

还有一种比较 hack 的做法，仅在 Linux 下用 C++ 验证过，不确定能否在其他操作系统及编程语言下实现。

上图描述了 32/64 位系统对内存地址的划分，不难发现，用户空间地址的最高位全部为 0。我们可利用这一点表示某个节点是否被访问过：

节点指针域的最高位为 0，表示该节点未被访问过。
节点指针域的最高位为 1，表示该节点已经被访问过了。

利用上述标记方法，可以用一个指针判断是否有环。下述代码可在 64 位系统上正确运行。

class Solution {
public:bool hasCycle(ListNode *pHead) {const uint64_t mask = 0x8000000000000000;while (pHead != nullptr && pHead->next != nullptr) {uint64_t &adr = *(uint64_t*)(&(pHead->next));if (adr & mask) {return true;}pHead = pHead->next;adr |= mask;}return false;}
};