环形链表之快慢指针

前言

对于环形链表，通过快慢指针，如果存在环，这这两个指针一定会相遇，这是一种经典的判断环或是应用于环问题的思想。

一、案例

1、环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

注：以O(1)内存进阶。

2、环形链表II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

注：不允许修改 链表。

注：以O(1)内存进阶

二、题解

1、环形链表

2、环形链表II

3、源码

package com.xhu.offer.tencent; import java.util.HashSet; import java.util.Set; //环形链表 public class HasCycle { 
    public boolean hasCycle(ListNode head) { 
    //一直next直到next == null 或者next到已经访问过的节点，分别返回true 和 false； Set<ListNode> mark = new HashSet<>(); while (head != null) { 
    if (mark.contains(head)) return true; mark.add(head); head = head.next; } return false; } //需要消耗O(1)内存来进阶 public boolean hasCycle2(ListNode head) { 
    //每向前走一步就改变链接方向，如果循环结束的最后一个节点是初始节点则有环。 if (head == null || head.next == null) return false; ListNode point = head, pre1 = null, pre2; while (point.next != null) { 
    //记录前向节点 pre2 = point; //往后遍历 point = point.next; //修改前向节点的next指向 pre2.next = pre1; //跟新pre1 pre1 = pre2; } return point == head; } //修改节点值 public boolean hasCycle3(ListNode head) { 
    while (head != null) { 
    if (head.val == Integer.MAX_VALUE) return true; head.val = Integer.MAX_VALUE; head = head.next; } return false; } //快慢指针O(1) public boolean hasCycle4(ListNode head) { 
    //快慢指针，如果有环，则一定会相遇。 if (head == null || head.next == null) return false; ListNode point1 = head, point2 = head.next; while (point2 != null) { 
    if (point1 == point2) return true; point1 = point1.next; point2 = point2.next; if (point2 == null) return false; point2 = point2.next; } return false; } //环形链表II public ListNode detectCycle(ListNode head) { 
    //以环形链表I的基础，返回节点即可 //一直next直到next == null 或者next到已经访问过的节点 Set<ListNode> mark = new HashSet<>(); while (head != null) { 
    if (mark.contains(head)) return head; mark.add(head); head = head.next; } return null; } //以O(1)内存进阶 public ListNode detectCycle2(ListNode head) { 
    //以环形链表I的基础，返回节点即可 //一直next直到next == null 或者next到已经访问过的节点 Set<ListNode> mark = new HashSet<>(); while (head != null) { 
    if (mark.contains(head)) return head; mark.add(head); head = head.next; } return null; } //以O(1)内存进阶，在不修改链表的情况。 public ListNode detectCycle3(ListNode head) { 
    //快慢指针，如果有环，则一定会相遇。这个时候就能确定这个相遇的点一定在环内。 //然后从头开始遍历到环内节点，寻找入环节点。 if (head == null || head.next == null) return null; ListNode point1 = head, point2 = head.next,end = null; while (point2 != null) { 
    if (point1 == point2) { 
    end = point1; break; } point1 = point1.next; point2 = point2.next; if (point2 == null) return null; point2 = point2.next; } if(end == null) return null; while(head != end){ 
    point1 = end.next; while(point1 != end){ 
    if(point1 == head) return point1; point1 = point1.next; } head = head.next; } return end; } // Definition for singly-linked list. class ListNode { 
    int val; ListNode next; ListNode(int x) { 
    val = x; next = null; } } } 

4、寻找入环点的数学解法

/* target：找到入环点。 快慢指针 找到相遇点，此时起始节点到达相遇点的距离是环长的N倍。 设新的起始点在环点，则从此处出发，到达起始点的距离 等于 环点再走n圈一致 - k。 而入环点未知，而起始点未知，根据两者关系，反推起始点。 */ public ListNode detectCycle(ListNode head) { 
    // bug2：毕竟要先do，所以需要先判断链表是否为null. if (head == null) return null; // bug1:fast = head == null ? null : head.next;这样会导致其先走了一步，导致反推入环口时发生死循环。 ListNode slow = head, fast = head; // 寻找相遇点。 do { 
    fast = fast.next; slow = slow.next; fast = fast == null ? null : fast.next; } while (slow != fast && fast != null); if (fast == null) return null; // 反推入环点。 slow = head; while (slow != fast) { 
    slow = slow.next; fast = fast.next; } return slow; } // Definition for singly-linked list. class ListNode { 
    int val; ListNode next; ListNode(int x) { 
    val = x; next = null; } } } 

// 非do while() class DetectCycle2 { 
    /* target：找到入环点。 快慢指针 找到相遇点，此时起始节点到达相遇点的距离是环长的N倍。 设新的起始点在环点，则从此处出发，到达起始点的距离 等于 环点再走n圈一致 - k。 而入环点未知，而起始点未知，根据两者关系，反推起始点。 */ public ListNode detectCycle(ListNode head) { 
    ListNode slow = head, fast = head == null ? null : head.next; // 寻找相遇点。 while (slow != fast && fast != null) { 
    fast = fast.next; slow = slow.next; fast = fast == null ? null : fast.next; } if (fast == null) return null; // 反推入环点。 slow = head; fast = fast.next;// a + b + 1 = kN while (slow != fast) { 
    slow = slow.next; fast = fast.next; } return slow; } // Definition for singly-linked list. class ListNode { 
    int val; ListNode next; ListNode(int x) { 
    val = x; next = null; } } } 

总结

参考文献