环形链表
我们在判断一个链表是否是环形的，即首尾相连，我们可以以使用快慢指针，如果快指针能再次追上慢指针，就说明该链表是环形的，这边可以举个操场跑步的例子，当操场是环形的，跑的快的，就可以对跑的慢的实现套圈.
判断环形链表
给你一个链表，如果其是环形链表，则返回 true 否则返回 false
存放到集合中
分析：通过集合里面查找来判断是否回到头指针，不建议
public boolean hasCycle(ListNode head) {
Set<ListNode> set = new HashSet<>();
while (head != null) {
//如果重复出现说明有环
if (set.contains(head))
return true;
//否则就把当前节点加入到集合中
set.add(head);
head = head.next;
}
return false;
}
快慢指针(快2慢1)
package LinkList;
public class roundList {
public class Solution {
class ListNode {
int val;
ListNode next;
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
public boolean hasCycle(ListNode head) {
if (head == null){
return false;
}
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;
}
}
}
先反转再比较
如果反转过后的头结点与原来的头结点相同，那么就是环形链表
反转原理：
- 先给头结点的下个结点赋值一个新结点 temp
- 然后把头结点的 next 指向一个新节点 newHead
- 然后把那个新节点 newHead 指向 头结点
- 然后再令头结点 为 temp (之前头结点的下一个结点)
在上面的流程中，temp充当相当于完成原来的链表的下个位置的指针，而newHead相当于是一种前驱指针的感觉，让原来在后面的元素指向前面的元素
public ListNode reverseList(ListNode head) {
//新链表
ListNode newHead = null;
while (head != null) {
//先保存访问的节点的下一个节点，保存起来
//留着下一步访问的
ListNode temp = head.next;
//每次访问的原链表节点都会成为新链表的头结点，
//其实就是把新链表挂到访问的原链表节点的
//后面就行了
head.next = newHead;
//更新新链表
newHead = head;
//重新赋值，继续访问
head = temp;
}
//返回新链表
return newHead;
}
public boolean hasCycle(ListNode head) {
ListNode rev = reverseList(head);
if (head != null && head.next != null && rev == head) {
return true;
}
return false;
}
快慢指针的一般化
我们可以知道快指针要追上慢指针 需要多跑至少“一圈”，即一个链表长度，假设为m，当然所需要的时间就是 = 需要的圈数 / (快指针的速度 - 慢指针的速度)
为什么说多跑至少一圈？不妨想，快指针的速度 - 慢指针的速度 为偶数，而链表长度为奇数，那么就会出现第一次快指针追慢指针时，它们位置没有重合，而是快指针直接超越慢指针的情况，那么 快指针需要再追一圈，此时的圈数 = 2 * m，就一定为偶数就能追上
所以 所需要的时间就是 = 需要的圈数 / (快指针的速度 - 慢指针的速度) 必须为整数，当速度差分之圈数不是整数时，就需要多跑几圈来实现整除(即快慢指针的位置重合)
当然上面假设的环可能是从链表某处开始形成的环，有可能不是整个链表是环形
注意：循环的条件是快指针当前的不为null，如果要一次前进 m 步(即 fast = fast.m next)(m 个 next)，那么就要保证其前面 m - 1个 next都不为null，否则会抛出空指针异常
代码(快3慢1)
ublic boolean hasCycle(ListNode head) {
if (head == null)
return false;
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next.next;
if (slow == fast)
return true;
}
return false;
}
代码(快5慢1)
public boolean hasCycle(ListNode head) {
if (head == null)
return false;
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null && fast.next.next != null && fast.next.next.next != null && fast.next.next.next.next != null) {
slow = slow.next;
fast = fast.next.next.next.next.next;
if (slow == fast)
return true;
}
return false;
}
代码(快3慢2)
public boolean hasCycle(ListNode head) {
if (head == null)
return false;
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null && fast.next.next != null) {
slow = slow.next.next;
fast = fast.next.next.next;
if (slow == fast)
return true;
}
return false;
}
环形链表II
给你给定一个链表的头节点 head ，返回链表开始入环的第一个节点(在哪里开始形成环的)。 如果链表无环，则返回 null
分析
注：来源于魏梦舒老师的《算法漫画》
主要抓住两点，第一次相遇两指针的关系，一个走的路程是另外一个两倍
代码
public class roundListPlus {
class ListNode{
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
next = null;
}
}
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
// 快指针每次移动2，慢指针每次移动1
// 用循环来寻找第一次相遇的点
while (fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if (fast == slow){
break;
}
}
// 循环结束要么是该表非环形，要么是快慢指针相遇
// 判断，如果非环形链表，直接返回 null
if ( fast == null || fast.next == null){
return null;
}
// 根据递推关系，此时把其中一个指针放回头结点，另一个指针在第一次相遇位置
// 此时两个指针一次都只移动1，下一次相遇就是入环结点
slow = head;
while (fast != slow){
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
}
