【每日力扣】141. 环形链表与142. 环形链表 II

🔥 个人主页: 黑洞晓威
😀你不必等到非常厉害，才敢开始，你需要开始，才会变的非常厉害

141. 环形链表

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

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

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

解题思路

为了判断链表中是否存在环，可以使用快慢指针的方法。快指针每次向前移动两步，慢指针每次向前移动一步，如果链表中存在环，快指针最终会追上慢指针，如果不存在环，快指针会到达链表尾部。

具体步骤如下：

1. 初始化快慢指针，快指针每次移动两步，慢指针每次移动一步。
2. 迭代遍历链表，如果快指针追上了慢指针，则链表存在环；如果快指针到达了链表尾部，则链表不存在环。

代码实现

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

142. 环形链表 II

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

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

不允许修改 链表。

解题思路

要寻找环形链表的入口节点，可以使用快慢指针的方法。当快慢指针相遇时，让其中一个指针重新指向头节点，并让两个指针以相同速度向前移动，再次相遇的节点就是环的入口节点。这个方法可以证明在相遇点后，再次相遇的节点就是环的入口。

具体步骤如下：

1. 使用快慢指针找到两指针相遇的节点。
2. 将其中一个指针重新指向头节点，保持另一个指针在相遇点。
3. 两个指针以相同速度向前移动，再次相遇的节点即为环的入口节点。

代码实现

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

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

        return null;
    }
}