142. 环形链表 II-526互联

2023-11-21

142. 环形链表 II - 力扣（LeetCode）

思路：

1 hashmap：将其next一个个存入，直到找到next已经存在的，这里用set就行

2 快慢指针，一个一步步走，一个一次走2步，自己画一下图，其一定会在环中相遇，且一定是多走一圈，然后相遇时，将慢指针保留，继续走，重新定义一个指针从一开始走，他们相等时就是入口

set：

/**
 * 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) {
        //要么无环，要么一个环   不会出现多个环的情况
        //set集合
 
        Set<ListNode> set=new HashSet<ListNode>();
 
        if(head==null){
            return null;
        }
 
        ListNode now=head;
 
        while(now.next!=null){
            if(set.contains(now.next)){
                return now.next;
            }
            set.add(now);
            now=now.next;
        }
 
        return null;
 
    }
}

快慢指针：

/**
 * 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) {
        //要么无环，要么一个环   不会出现多个环的情况
       
       //经典的快慢指针   都是从开头开始，一个是每次走2步，一个是每次走一步，有环最终一定会相遇的
       //使用O（1）空间解决问题
 
        if(head==null){
            return null;
        }
 
        ListNode slow=head;
        ListNode fast=head;
 
        while(slow!=null && fast!=null && fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if(slow==fast){
                ListNode temp=head;
                while(temp!=slow){
                    temp=temp.next;
                    slow=slow.next;
                }
                return slow;
            }
        }
 
        return null;
 
 
    }
}