leetcode--环形链表.找到入环节点（java）-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode--环形链表.找到入环节点（java）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

环形链表.找到入环节点

LeetCode 142：环形链表II 可以在这里测试

题目描述

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

示例1：
leetcode--环形链表.找到入环节点（java）

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

示例2：
leetcode--环形链表.找到入环节点（java）

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

示例3：
leetcode--环形链表.找到入环节点（java）

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

解题思路

这里用到一个小技巧，快慢指针法：
1.环形链表没有尾结点，会在环里循环，因此，如果能走到null ，就表示无环，
2.有环时，使用快慢指针法，快指针一次走两步，慢指针一次走一步，一定会在环内相遇，
3.相遇后，快指针回到头节点，然后改成每次走一步，慢指针还是走一步。然后就会在入环节点相遇。
4.上面的结论，自己可以试着证明下。

代码如下：

/**
 * 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) {
    	//环形链表 没有null 节点，如果走到null 说明无环，
        if(head == null || head.next == null || head.next.next == null){
            return null;
        }
        //快的先走两步，慢的走一步
        ListNode fast = head.next.next;
        ListNode slow = head.next;
        //先让快慢指针相遇
        while(fast != slow){
        		//遇到null 说明无环
            if(fast.next == null || fast.next.next == null){
                return null;
            }
            fast = fast.next.next;
            slow = slow.next;
        }

			//快指针回到头节点，开始一次走一步，就会在入环节点相遇
        fast = head;
        while(fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}