【LeetCode力扣142】环形链表Ⅱ,给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回null。

目标&＃xff1a;熟练运用Java所学知识

本文内容&＃xff1a;使用Java实现&＃xff1a;环形链表Ⅱ

给定一个链表&＃xff0c;返回链表开始入环的第一个节点。 如果链表无环&＃xff0c;则返回 null。为了表示给定链表中的环&＃xff0c;我们使用整数 pos 来表示链表尾连接到链表中的位置&＃xff08;索引从 0 开始&＃xff09;。 如果 pos 是 -1&＃xff0c;则在该链表中没有环。注意&＃xff0c;pos 仅仅是用于标识环的情况&＃xff0c;并不会作为参数传递到函数中。

说明&＃xff1a;不允许修改给定的链表。

示例 1&＃xff1a;

输入&＃xff1a;head &＃61; [3,2,0,-4], pos &＃61; 1
输出&＃xff1a;返回索引为 1 的链表节点
解释&＃xff1a;链表中有一个环&＃xff0c;其尾部连接到第二个节点。

示例 2&＃xff1a;

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

示例 3&＃xff1a;

输入&＃xff1a;head &＃61; [1], pos &＃61; -1
输出&＃xff1a;返回 null
解释&＃xff1a;链表中没有环。

• 第一步&＃xff1a;排除空链表和只有一个节点的情况

//排除空链表和只有一个节点的情况if(head&＃61;&＃61;null||head.next&＃61;&＃61;null){return null;}


• 第二步&＃xff1a;判断链表是否带环

//通过循环判断链表是否带环while(fast!&＃61;null&&fast.next!&＃61;null){fast&＃61;fast.next.next;slow&＃61;slow.next;if(fast&＃61;&＃61;slow){//表示链表带环&＃xff0c;结束循环break;}}


• 第三步&＃xff1a;如果链表没有环&＃xff0c;则返回空

//判断上述while循环结束的原因&＃xff0c;只有两个原因//第一个原因&＃xff1a;如果快指针走到了链表结尾&＃xff0c;则返回nullif(fast&＃61;&＃61;null||fast.next&＃61;&＃61;null){return null;}


• 第四步&＃xff1a;链表带环&＃xff0c;找到链表入环的第一个结点

如果链表带环&＃xff0c;则 快慢指针相遇的结点 和 链表头结点 距离链表入环的第一个结点是相同的所以只需要同步遍历&＃xff0c;直到第一次相遇既为链表入环的第一个结点

//第二个原因&＃xff1a;链表带环//如果链表带环&＃xff0c;则 快慢指针相遇的结点 和 链表头结点 距离链表入环的第一个结点是相同的//所以只需要同步遍历&＃xff0c;直到第一次相遇既为链表入环的第一个结点while(cur!&＃61;fast){cur&＃61;cur.next;fast&＃61;fast.next;}return fast;

实现代码:

public static ListNode detectCycle(ListNode head) {//排除空链表和只有一个节点的情况if(head&＃61;&＃61;null||head.next&＃61;&＃61;null){return null;}ListNode slow&＃61;head;//慢指针ListNode fast&＃61;head;//快指针ListNode cur&＃61;head;//通过循环判断链表是否带环while(fast!&＃61;null&&fast.next!&＃61;null){fast&＃61;fast.next.next;slow&＃61;slow.next;if(fast&＃61;&＃61;slow){//表示链表带环&＃xff0c;结束循环break;}}//判断上述while循环结束的原因&＃xff0c;只有两个原因//第一个原因&＃xff1a;如果快指针走到了链表结尾&＃xff0c;则返回nullif(fast&＃61;&＃61;null||fast.next&＃61;&＃61;null){return null;}//第二个原因&＃xff1a;链表带环//如果链表带环&＃xff0c;则 快慢指针相遇的结点 和 链表头结点 距离链表入环的第一个结点是相同的//所以只需要同步遍历&＃xff0c;直到第一次相遇既为链表入环的第一个结点while(cur!&＃61;fast){cur&＃61;cur.next;fast&＃61;fast.next;}return fast;}