当前位置：首页 > news >正文

【Hot100】LeetCode—142. 环形链表 II

news 2025/12/3 12:15:57

1- 思路

快慢指针+推导

① 利用快慢指针，定位环
② 根据环，从头出发一个指针，从环处出发一个指针
- 两者相遇的地方就是环的入口

2- 实现

⭐142. 环形链表 II——题解思路

在这里插入图片描述

public class Solution {public ListNode detectCycle(ListNode head) {if(head==null){return head;}ListNode slow = head;ListNode fast = head;while(fast.next!=null && fast.next.next!=null){slow = slow.next;fast = fast.next.next;if(slow==fast){ListNode index1 = head;ListNode index2 = slow;while(index1!=index2){index1 = index1.next;index2 = index2.next;}return index1;}}return null;}   
}

3- ACM 实现

public class hashCycle {public static class ListNode {int val;ListNode next;ListNode(int x) {val = x;next = null;}}public static ListNode detectCycle(ListNode head) {if(head==null){return head;}ListNode slow = head;ListNode fast = head;while(fast.next!=null && fast.next.next!=null){slow = slow.next;fast = fast.next.next;if(slow==fast){ListNode index1 = head;ListNode index2 = slow;while(index1!=index2){index1 = index1.next;index2 = index2.next;}return index1;}}return null;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("输入链表长度");int n = sc.nextInt();ListNode head = null,tail=null;for(int i = 0 ; i < n;i++){ListNode nowNode  = new ListNode(sc.nextInt());if(head==null){head = nowNode;tail = nowNode;}else{tail.next = nowNode;tail = nowNode;}}System.out.println("输入环的位置");int index = sc.nextInt();ListNode cycleNode = head;while (index>0){cycleNode = cycleNode.next;index--;}tail.next = cycleNode;System.out.println("结果是"+detectCycle(head).val);}
}