leetcode 链表有环、环入口节点、环长等相关问题解答

1、给定一个链表，判断链表中是否有环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。 主要思想：用快慢指针判断，两种写法。

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null)
            return false;
        ListNode slow = head;
        ListNode fast = head;
        while (true){
            if(fast == null || fast.next == null)
                return false;
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast)
                return true;
        }
    }
}

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null)
            return false;
        ListNode slow = head;
        ListNode fast = head.next; //注意这里要设置不一样的起点
        while (slow != fast) {
            if(fast == null || fast.next == null)
                return false;
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}

2、给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

1、 用Set去重原理判断

import java.util.*;
public class Solution {
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        while(head != null){
            if(!set.contains(head)){
                set.add(head);
            }else{
                return head;
            }
            head = head.next;
        }
        return null;
    }
}

1、 快慢指针(需要推导一下)

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null)
            return null;
        ListNode slow = head;
        ListNode fast = head;
        while (true){
            if(fast == null || fast.next == null)
                return null;
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast)
                break;
        }

        fast= head;
        while (slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }
}

3、链表有环，求环形链表的长度。

思路: 在判断有环并且找到快慢指针碰撞点时,在碰撞点进一步用快慢指针，并且用length变量计数，二者再次相遇时，length即为环长。

public class CircleList {
    static int length = 0;

    public static int hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (true) {
            if (fast == null || fast.next == null)
                return 0;
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                while (true) {
                    slow = slow.next;
                    fast = fast.next.next;
                    length++;
                    if (slow == fast)
                        return length;
                }

            }
        }
    }

    public static void main(String[] args) {
        ListNode node = new ListNode(5);
        ListNode node1 = new ListNode(3);
        ListNode node2 = new ListNode(7);
        ListNode node3 = new ListNode(2);
        ListNode node4 = new ListNode(6);
        ListNode node5 = new ListNode(8);
        ListNode node6 = new ListNode(1);
        node.next = node1;
        node1.next = node2;
        node2.next  = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node3;
        int i = hasCycle(node);
        System.out.println(i);
    }
}

文章永久链接：https://tech.souyunku.com/27981