leedcode【142】. 环形链表 II——Java解法
Problem: 142. 环形链表 II
- 思路
- 解题方法
- 复杂度
- Code
- 性能
思路
1.用快慢指针找到相遇的点（快指针一次走一步，慢指针一次走两步）
2.一个指针从head开始，一个指针从相遇点开始，一次一步，相遇处即为环入口
解题方法
详解见链接：
https://programmercarl.com/%E9%93%BE%E8%A1%A8%E6%80%BB%E7%BB%93%E7%AF%87.html#%E9%93%BE%E8%A1%A8%E7%BB%8F%E5%85%B8%E9%A2%98%E7%9B%AE
复杂度
时间复杂度:
O(n)
空间复杂度:
O(1)快慢指针相遇前，指针走的次数小于链表长度，快慢指针相遇后，两个index指针走的次数也小于链表长度，总体为走的次数小于 2n
Code
Java
/*** 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) {//先找相遇节点ListNode fast = head; // 快指针，一次走两步ListNode slow = head; // 慢指针，一次走一步//找快慢指针相遇节点while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;if(fast == slow){ListNode index1 = fast;ListNode index2 = head;while(index1 != index2){index1 = index1.next;index2 = index2.next;}return index1;}}return null;}
}性能
