LeetCode142之环形链表II

本文主要是介绍LeetCode142之环形链表II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目

二、一种解题思路

①方法介绍一：龟兔赛跑法升级版

    方法解析：①使用龟兔赛跑法先判断当前链表是否存在环（快慢指针能够相遇，则存在环）
                      ②假设链表头部到环起点的距离为x，环的长度为y，快指针每次走两步，慢指针每次走一步，

                        慢指针走t步后与快指针相遇，相遇的位置是(t - x)%y + x=(2*t - x)%y + x,求得t%y = 0
                        也就是说t是y的整数倍，故从链表头部和相遇的位置一起走x步会重新相遇。

   时间复杂度：O(n)

   空间复杂度：O(n)

②核心代码：

/*** 查找环形链表的入环节点* 方法: ①使用龟兔赛跑法先判断当前链表是否存在环（快慢指针能够相遇，则存在环）* ②假设链表头部到环起点的距离为x，环的长度为y，快指针每次走两步，慢指针每次走一步，* 慢指针走t步后与快指针相遇，* 相遇的位置是(t - x)%y + x=(2*t - x)%y + x,求得t%y = 0* 也就是t是y的整数倍，故从链表头部和相遇的位置一起走x步会重新相遇。** @param head 头节点* @return 环形链表的入环节点*/public static ListNode detectCycle1(ListNode head) {if (head == null || head.next == null) {return null;}ListNode target1 = head;ListNode target2 = head;while (target1 != null && target2 != null) {target1 = target1.next;if (target2.next != null) {target2 = target2.next.next;} else {target2 = target2.next;}if (target1 == target2) {break;}}if (target1 == target2) {target1 = head;while (target1 != target2) {target1 = target1.next;target2 = target2.next;}return target1;}return null;}

③辅助类

public class ListNode {public int val;public ListNode next;public ListNode(int x) {val = x;next = null;}@Overridepublic String toString() {return "ListNode{" +"val=" + val + "}";}
}

三、LeetCode成功截图

四、感想

加油，加油，再加油，坚持，坚持，再坚持。

这篇关于LeetCode142之环形链表II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---