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

【LeetCode-中等题】142. 环形链表 II

news 2025/7/1 22:35:06

文章目录

- 题目
- 方法一：哈希表set去重
- 方法二：快慢指针

题目

在这里插入图片描述

方法一：哈希表set去重

思路：我们遍历链表中的每个节点，并将它记录下来；一旦遇到了此前遍历过的节点，就可以判定链表中存在环。借助哈希表可以很方便地实现。

   public ListNode detectCycle(ListNode head) {if(head == null) return null;if(head.next==null) return null;if(head.next.next == head) return head;Set<ListNode> NodeSet = new HashSet<>();while(head != null){if(NodeSet.add(head)){head =head.next;continue;}else return head;}return null;}

方法二：快慢指针

第一次快慢指针相遇后。马上让新指针ptr从head 和slow同步走，最终会在环点相遇

在这里插入图片描述

public ListNode detectCycle(ListNode head) {if (head == null) return null;ListNode fast = head;//快指针ListNode slow = head;//慢指针while(fast!=null){//满足快指针不空指针异常（fast.next.next!=null）//移动指针slow = slow.next;if(fast.next !=null) fast = fast.next.next;else return null;if(fast==slow) {//说明一定有环了ListNode ptr = head;//定义新指针从head出发while(ptr != slow){ptr = ptr.next;slow = slow.next;}return ptr;}}return null;}