前言

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

一、案例

1、环形链表

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

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

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

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

2、环形链表II

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

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

注：不允许修改 链表。

注：以O(1)内存进阶

二、题解

1、环形链表

1）可以直接遍历，把遍历的结点用Set记录下来，然后记录前查看set中是否有该节点。
2）对于O(1)内存进阶，
A）可以通过修改遍历过的节点的value为一个特殊值，然后一直遍历，如果中途碰到有value为特殊值，说明遍历过，即有环。
B）可每次遍历过之后，就修改前驱节点的next指向为相反的指向，不管是否有环，都不会在遍历中出现死循环，而是从左出即有环，从右出则无环。
C）快慢指针，可以通过快慢指针，就像在操场跑圈一样，速度快的能和速度慢能相遇。

2、环形链表II

1）从第一个的基础上，1）和2）的A）两种方式上都容易修改得来；而B）不适用；
2）对于C），可以得到最后相遇的地方，这个节点一定在环内，设为end节点。外层从头节点遍历到end节点，内层循环从end节点开始遍历，直到下一个end节点，看中途是否会碰到外层循环的中途节点。

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;
        }
    }
}

总结

1）还是注意观察问题的个性之处，思考其中的细节，而不是简单的算法应用，比如修改节点的值或是修改节点的next指针。算法思想和代码只是工具，重要的是特定问题中的抽象逻辑。
2）对于简单应用，就是熟练使用set。
3）掌握快慢指针这样的经典算法思想，碰到环就得触发快慢指针的记忆，这样才显得专业一点。

参考文献

[1]LeetCode 环形链表
[2]LeetCode 环形链表II

今天的文章环形链表之快慢指针分享到此就结束了，感谢您的阅读。