1.判断链表是否带环
环形链表
题目:
给你一个链表的头节点 head ,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。
如果链表中存在环,则返回 true 。 否则,返回 false 。示例:
⭐思路:采用快慢指针的方法,快指针一次走两步,慢指针一次走一步,如果链表带环的话,两个指针将会在环中相遇,如果不带环,快指针将会先到达链表的末尾。
👁🗨参考代码:
public class Solution { 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; //快指针优先到达链表末尾,说明不带环 } }
🤔思考:
1. 为什么快指针一次走两步,慢指针一次走一步可以?
因为,如果链表带环,快指针先进入环,慢指针后进入环,快指针每次比慢指针多走一步,在环中两个指针的距离每次减少一步,直到距离为0,所以这种走法可以。
2. 快指针一次走3步,4步......n步可以吗?
假设快指针走3步,慢指针走1步,快指针优先进入环,慢指针后进入环,看如下情况:
🍊 也就是说只有快指针一次走2步,慢指针一次走1步,才能在任何情况下都能相遇,其他走法或多或少会出点问题。
2.返回带环链表的第一个入环结点
环形链表Ⅱ
题目:
给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。
不允许修改 链表。 示例:
🤔思路:这里记住一个结论:让一个指针从链表起始位置开始遍历链表,同时让一个指针从判环时相遇点的位置开始绕环运行,两个 指针都是每次均走一步,最终肯定会在入口点的位置相遇。
⭐证明过程:
对此图进行说明:H为链表起始点,E为入环点,M为判环时相遇点
设:环的长度为R,H到E的距离为L,E到M的距离为X,则M到E的距离为R-X
判环时快慢指针所走的长度:
fast:L+X+nR slow:L+X
注意:
1. 当慢指针进入环时,快指针可能已经在环中走了n圈了
2. 慢指针进入环时,快指针肯定会在慢指针走一圈之内追上慢指针
快指针的速度为慢指针的两倍,则有如下关系:
2*(L+X) = L+X+nR
L+X = nR
L = nR - X(n为1,2,3,4......n的大小取决于环的大小,环越小,n越大)
极端情况下,假设n=1,此时:L = R - X ,即:一个指针从链表起始位置开始走,一个指针从判环相遇点环绕,每次都走一步,最终两个指针会在环的入口点相遇
👁🗨参考代码:
public class Solution { public ListNode detectCycle(ListNode head) { //判断链表是否带环 ListNode fast = head; ListNode slow = head; Boolean isCircle = false; while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; if(fast == slow){ isCircle = true; break; } } if(isCircle == false){ return null; } //链表带环,求入环的第一个节点 ListNode pH = head; //链表头 ListNode pM = fast; //判环相遇点 while(pH != pM){ pH = pH.next; pM = pM.next; } return pH; } }