环形链表概念
环形链表是一种特殊类型的链表数据结构,其最后一个节点的地址域不为null,而是指向了链表中的某个节点,形成一段闭环,如下图:
tip:该类型题目不能以判断 cur.next 是否为 null 为循环条件,否则死循环
判断是否为环形链表
给一个链表的头节点 head
,判断链表中是否有环,如果链表中存在环 ,则返回 true
。 否则,返回 false
。
思路:
- 使用快慢指针(fast、slow),快指针每次移动两步,慢指针每次移动一步,两指针从链表起始位置走,若链表带环,则一定相遇
- 以 fast != null (对应偶数节点情况) && fast.next != null (对应奇数节点情况) 为循环条件
- 若 fast 与 slow 相遇,则是环形链表,返回 true
- 若循环结束,则未相遇,即不是环形链表,返回 false
代码:
public boolean hasCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if(fast == slow) {
return true;
}
}
return false;
}
扩展:若快指针走3步、4步、n步是否可行
假设快指针每次走三步,慢指针每次走一步,此时快指针先进环,慢指针后进环,假设慢指针进环时,快指针的位置如下图所示:
这种情况下,快指针每次走3步,慢指针每次走1步,快指针刚好将慢指针套圈,永远不会相遇
当快指针每次走3步,慢指针每次走2步,他们差值为1,此时才会相遇
但是循环条件就要发生改变:
while(fast.next != null && fast.next.next != null) {
这样代码更复杂,得不偿失,因此最优解为快指针每次走2步,慢指针每次走1步
环形链表求入口点
给定一个链表的头节点 head
,返回链表开始入环的第一个节点。 如果链表无环,则返回 null
。
思路:这里涉及到一个简单的数学问题,如下图:
假设环的长度为C,起始点到入口点的距离为X,相遇点到入口点的距离为Y
快指针每次走2步,慢指针每次走1步,当他们相遇时,快指针走的步数是慢指针的2倍,所以得出以下等式:
(slow所走路程的2倍) 2* (X + C - Y) = X + C + (C - Y) (fast所走的路程)
计算可得 X = Y
说明起始点到入口点的距离 和 相遇点到入口点的距离是相同的
当我们以相同速度一个从起始点出发,一个从相遇点出发,再次相遇就是入口点
代码:
public ListNode detectCycle(ListNode head) {
//先求相遇点
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if(fast == slow) {
break;
}
}
if(fast == null || fast.next == null) {
return null;
}
//让fast回到起始点,以和slow一样的速度往后走
//slow从相遇点开始走
fast = head;
while(fast != slow) {
fast = fast.next;
slow = slow.next;
}
return fast;//该fast即为入口点
}
另一种情况:环的长度远远小于起始点到入口点的长度,即Y不等于X
这种情况下,假设slow绕环N次后与fast在相遇点处相遇,距离公式变为:
(slow所走路程的2倍) 2* (X + C - Y) = X + NC + (C - Y) (fast所走的路程)
计算可得:X = (N-1)*C + Y
当N等于1时,就是上面 X = Y 的例子,X = Y 是所有情况中的一种特殊情况,代码无需改动