判断链表有环

有一个单向链表，如何判断链表是否为有环链表？

HashSet法

思路

• 创建一个以节点ID为Key的HashSet集合
• 遍历链表并加入HashSet，判断是否重复，重复则有环

复杂度

• 时间复杂度O(n)
• 空间复杂度O(n)

双指针追及法

思路

• 声明两个指针p1，p2，都指向头节点
• p1为慢指针，速度一个节点，p2为快指针，速度两个节点，速度差一个节点
• 让两个指针开始跑，两个指针跑完一次，判断两个指针指向的节点是否相同，相同则有环，不同则继续下一次循环
  这个思路类似于数学上的 追及问题，如果跑道是环形的，快指针会追上慢指针

复杂度

• 时间复杂度O(n)
• 空间复杂度O(1)

源码

public static boolean isCycle(Node head){
    Node p1 = head, p2 = head;

    while(p2 != null && p2.next != null){
        p1 = p1.next;
        p2 = p2.next.next;

        //ringMeetNode可以在这里获得
        if(p1 == p2)
            return true;
    }

    return false;
}

/*
public class Node{
    int data;
    Node next;
    Node(int data){
        this.data = data;
    }
}

问题扩展

1.如何求出环的长度

当两个指针首次相遇，让两个指针接着前进，并统计前进的循环次数，直到两个指针再次相遇。此时统计前进的循环次数就是环长。

原理

p1与p2速度差为一个节点，当快指针再次追上慢指针时，快指针多走了慢指针一圈，因此：
环长 = 快指针走的步数 - 慢指针走的步数 = 速度差 * 前进次数 = 前进次数

代码实现

public int getRingLength(Node ringMeetNode){
    int ringLength = 0;
    //ringMeetNode可以在isCycle()中获得
    Node p1 = ringMeetNode, p2 = ringMeetNode;

    while(true){
        p1 = p1.next;
        p2 = p2.next.next;
        ringLength++;
        if(p1 == p2)
            break;
    }

    return ringLength;
}

2.如何求入环节点

原理

假设从链表头节点到入环的距离时D，从入环点到首次相遇点的距离时S1，从首次相遇点回到入环点的距离时S2

1. 两次指针首次相遇时，各自所走的距离：

• p1：D + S1
• p2：D + S1 + S2 + S1 = D + 2S1 + S2

2. 由于p2的速度是p1的两倍，因此：2(D + S1) = D + 2S1 + S2
3. 得到 D = S2，即：从头节点到入环点的距离 = 从首次相遇点回到入环点的距离
4. 这样一来，只要把其中一个指针放回头节点，另一个指针保持在远处，然后两个指针的 速度都是一个节点，那么：它们 相遇节点就是入环节点

代码实现

public Node getRingStart(Node head){
    //ringMeetNode可以在isCycle()中获得
    Node p1 = head, p2 = ringMeetNode;

    while(p1 != p2){
        p1 = p1.next;
        p2 = p2.next;
    }

    return p1;
}