一, 判断单链表是否存在环
这个问题有很多方法, 最容易想到的就是记录每个节点记录的次数. 这里也介绍的是另一种简单而常见的方法
快慢指针法:
定义两个指针 slow, fast.slow 指针一次走 1 个结点, fast 指针一次走 2 个结点. 如果链表中有环, 那么慢指针一定会再某一个时刻追上快指针(slow == fast). 如果没有环, 则快指针会第一个走到 NULL
- int has_cycle(node *head) {
- if (head == NULL) return false;
- node* fast = head;
- node* slow = head;
- while (1)
- {
- if (slow->next != NULL) slow = slow->next; // 慢指针走一步
- else return false;
- if (fast->next != NULL && fast->next->next != NULL) fast = fast->next->next; // 快指针走两步
- else return false;
- if (slow == fast) return true;
- }
- }
二, 寻找环的入口点
其中一个回到起点:
当 fast 按照每次 2 步, slow 每次一步的方式走, 发现 fast 和 slow 重合, 确定了单向链表有环路. 接下来, 让 fast 回到链表的头部, 重新走, 每次步长 1, 那么当 fast 和 slow 再次相遇的时候, 就是环路的入口了.
证明:
在 fast 和 slow 第一次相遇的时候, 假定 slow 走了 n 步, 环路的入口是在 p 步, 那么
slow 走的路径: p+c = n;(1) c 为 fast 和 slow 相交点 距离环路入口的距离
fast 走的路径: p+c+k*L = 2*n;(2), L 为环路的周长, k 是整数
fast 从头开始走, 步长为 1.
经过 n 步, fast 和 slow 都会到达 p + c 这一点. 将 (2)-(1) 得 k*L = n, 说明 n 是 L 的倍数, 同时 p + c = n,
所以 fast 和 slow 都走 p 步时, fast 距 (p + c) 差 c,slow 还差 c 回到(p + c), 所以 p 是他们的第一个交点, 之后的轨迹就一模一样了.
- node* find_loopport(node * head)
- {
- node* fast = head;
- node* slow = head;
- // 两个互指不考虑
- // 判断是否存在环, 如果存在得到相遇位置
- while (fast && fast->next)
- {
- slow = slow->next;
- fast = fast->next->next;
- if (fast == slow) break;
- }
- //fast 到达 NULL, 表示不存在环
- if (fast == NULL || fast->next == NULL) return NULL;
- // 将一个指针移到开始处, 步长都变成一
- fast = head;
- while (slow != fast)
- {
- slow = slow->next;
- fast = fast->next;
- }
- return slow;
- }
来源: http://www.bubuko.com/infodetail-2760736.html