本文主要是介绍leetcode刷题（38）——142. 环形链表 II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。
解法1:还是先用快慢指针找出是否是环形链表，同时记住停下来的节点fast,然后另一个指针从头节点开始出发，2个指针都移动1步，最后相遇的地方的节点就是环形链表的开始
public class Solution {public ListNode detectCycle(ListNode head) {if(head==null){return null;}ListNode in = getIntersect(head);if (in==null){return null;}ListNode p1 = head;ListNode p2 = in;while (p1!=p2){p1=p1.next;p2=p2.next;}return p1;}private ListNode getIntersect(ListNode head){ListNode fast = head;ListNode slow = head;while (fast!=null&&fast.next!=null){fast = fast.next.next;slow = slow.next;if (fast==slow){return fast;}}return null;}
}
需要注意几个点：
1.抽象出getIntersect方法来获取快的ListNode
2.getIntersect方法返回的对象需要判空
ListNode in = getIntersect(head);if (in==null){return null;}
解法2:使用set集合存放经历过的节点，循环中第一个在set里的节点一定是环形的入口
public class Solution {public ListNode detectCycle(ListNode head) {Set<ListNode> visited = new HashSet<ListNode>();ListNode node = head;while (node != null) {if (visited.contains(node)) {return node;}visited.add(node);node = node.next;}return null;}
}
这篇关于leetcode刷题（38）——142. 环形链表 II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
