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

题目

方法一：哈希表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;}