链表环问题

解决一个链表是否有环的问题

链表环问题需求

问题一：如何判断一个链表是否有环

问题二：求环的长度

问题三：求入环节点

分析如下：

实现如下

public class Main {
    private static class Node{
        int data;
        Node next;
        Node(int data){
            this.data = data;
        }
    }

    /**
     * 双指针判断是否有环
     * @param node
     * @return
     */
    private static boolean isCycle1(Node node) {
        Node p1 = node;
        Node p2 = node;
        while (p2!=null && p2.next!=null){
            p1 = p1.next;
            p2 = p2.next.next;
            // 利用追及问题的思想，如果有环，那么速度快的节点一定会超越速度慢的节点
            if(p1 == p2){
                //相遇在这一点，即可证明有环
                return true;
            }
        }
        return false;
    }

    /**
     * 求是否有环，并且求出长度
     * @param node
     * @return
     */
    private static boolean isCycle2(Node node) {
        Node p1 = node;
        Node p2 = node;
        while (p2!=null && p2.next!=null){
            p1 = p1.next;
            p2 = p2.next.next;
            if(p1 == p2){
                //有环，由于p2速度是p1的两倍，所以 环长 = (速度差)*前进次数 = 前进次数
                int count = 0;
                while ( count==0 || p1 != p2){
                    p1 = p1.next;
                    p2 = p2.next.next;
                    count++;
                }
                System.out.println("环长度为："+count);
                return true;
            }
        }
        return false;
    }

    /**
     * 求是否有环、以及入环点
     * @param node
     * @return
     */
    private static boolean isCycle3(Node node) {
        Node head = node;
        Node p1 = node;
        Node p2 = node;
        while (p2!=null && p2.next!=null){
            p1 = p1.next;
            p2 = p2.next.next;
            if(p1 == p2){
                p1 = head;
                int count = 0;
                while (count==0 || p1!=p2){
                    p1 = p1.next;
                    p2 = p2.next;
                    count++;
                }
                System.out.println("入环点在"+p1.data);
                System.out.println("头到入环点的距离有"+count+1);
                return true;
            }
        }
        return false;
    }
    
    /**           8 <- 2
     *            ↓    ↑
     *  3 -> 9 -> 6 -> 7
     * @param args
     */
    public static void main(String[] args) {
        Node node1 = new Node(3);
        Node node2 = new Node(9);
        Node node3 = new Node(6);
        Node node4 = new Node(7);
        Node node5 = new Node(2);
        Node node6 = new Node(8);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node3;
        System.out.println(isCycle3(node1));
    }

}

在LeetCode也刷到了这个题，发现算法逻辑有点问题，具体看代码

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        // 这里防止Head发来null或者只有一个结点的情况
        if(head==null||head.next==null){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        boolean isCycle = false;
        while(fast!=null && slow!=null){
            slow = slow.next;
            if(fast.next==null){
                // 进入循环前只判断了fast是否为空，在这里判断fast.next，以防使用fast.next.next报错， 如果fast.next为空则说明肯定没有环
                return null;
            }
            fast = fast.next.next;
            if(fast == slow){
                // 相遇
                isCycle = true;
                slow = head;
                while(fast!=slow){
                    slow = slow.next;
                    fast = fast.next;
                }
                break;
            }
        }
        if(!isCycle){
            // 无环返回null值
            return null;
        }else{
            return slow;
        }
    }
}