环形链表 —— 小灰的算法之旅读书笔记

环形链表

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/linked-list-cycle

题目描述

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

思路

双重循环,暴力破解

从头开始遍历,记录走过的步数(n),每经过一个节点,从头结点开始走n-1步,如果在走的过程中某个节点和最新的节点相同,那么就有环,否则就继续遍历,直到遍历完成,则证明无环

使用HashSet存储

从头开始遍历,每经过一个,判断HashSet中是否存在该节点,如果存在则有环,否者添加到HashSet中,然后继续遍历,直到遍历完成,则证明无环

双指针法

使用两个指针,一个指针走一步(慢指针),一个走两步(快指针),如果快指针和慢指针相遇了,则证明有环,如果快指正遍历完成了,则证明无环

代码实现

class ListNode {
    int data;
    ListNode next;

    public ListNode() {
    }

    public ListNode(int data) {
        this.data = data;
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "data=" + data +
                '}';
    }
}
public class Solution {
    public boolean hasCycle(ListNode head) {
        //慢指针
        ListNode p1 = head;
        //快指针
        ListNode p2 = head;
        //只需要判断快指针就可以了
        while (p2 != null && p2.next != null) {
            //走一步
            p1 = p1.next;
            //走两步
            p2 = p2.next.next;
            if (p1 == p2) {
                return true;
            }
        }
        return false;
    }
}

扩展

如果有环,求出环的长度

当第一次相遇的时候开始计数,当再次相遇的时候,快指正走过的路程比慢指正走过的路程多一圈,这一圈的长度就是环的长度

在第一次相遇的时候并不能知道环的长度,快指指针走过的路程比慢指针走过的路程多n(n>=1)圈,不一定是一圈

代码实现

public class Solution {

    /** * 求链表环的长度 * @param head 链表 * @return -1 表示没有环, */
    public int cycleLength(ListNode head) {
        //慢指针
        ListNode p1 = head;
        //快指针
        ListNode p2 = head;
        //p1走过的距离, p2走过的距离
        int x1 = 0, x2 = 0;
        //是否有环
        boolean hasCycle = false;
        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
            //如果存在环
            if (hasCycle) {
                x1 += 1;
                x2 += 2;
            }
            if (p1 == p2) {
                if (hasCycle) {
                    return x2 - x1;
                }
                hasCycle = true;
            }
        }
        return -1;
    }
}

返回链表开始入环的第一个节点

头节点到入环点的距离为D,入环点到首次相遇点的距离为S1,首次相遇点到入环点为S2,则存在

慢指针走过的距离 = D + S1

快指针走过的距离 = D + S1 + n*(S1 + S2), (n >= 1)

因为快指正走一格,慢指针走两格,所以存在

快指针走过的距离 = 慢指针走过的距离 * 2

D + S1 + n*(S1 + S2) = (D + S1) * 2

所以D = (n - 1)*(S1 + S2) + S2

让两个指针一个指向头节点,一个指向首次相遇点,两个指针每次都走一步,当两个指针相遇的那个节点就是入环节点

代码实现

public class Solution {

    /** * 返回入环节点 * @param head 链表 * @return null表示没有环,其他表示入环节点 */
    public ListNode meetNode(ListNode head) {
        //慢指针
        ListNode p1 = head;
        //快指针
        ListNode p2 = head;
        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
            if (p1 == p2) {
                //从头开始
                ListNode result = head;
                while (true) {
                    //必须先判断后移动
                    if (result == p1) {
                        return result;
                    }
                    result = result.next;
                    p1 = p1.next;

                }
            }
        }
        return null;
    }
}