142. 环形链表II

双指针法

class Solution {
    public ListNode detectCycle(ListNode head) {

        /**
         * 1、判断是否存在环形链表:创建快慢指针,从头节点出发,如果两个指针能相遇,说明存在环形链表
         * 2、找到环形入口:在链表头节点和快慢指针相遇的节点分别创建两个指针,同步遍历,一旦相遇即是环形入口
         */
        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null){

            fast = fast.next.next;
            slow = slow.next;

            /**
             * 如果相遇,则继续寻找环形入口
             */
            if (fast == slow){

                ListNode left = head;
                ListNode right = fast;

                while (left != right){

                    left = left.next;
                    right = right.next;
                }

                return left;
            }
        }

        return null;
    }
}

/**
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 */

哈希表

class Solution {
    public ListNode detectCycle(ListNode head) {

        /**
         * 记录下每次遍历的节点,如果遇到相同的就返回
         */
        HashSet<ListNode> set = new HashSet<>();
        ListNode cur = head;

        while (cur != null){

            if (set.contains(cur)){
                return cur;
            }

            set.add(cur);
            cur = cur.next;
        }

        return null;
    }
}

/**
 * 时间复杂度 O(n)
 * 空间复杂度 O(n)
 */

https://leetcode-cn.com/problems/linked-list-cycle-ii/

上一篇:代码随想录:链表


下一篇:腾讯五十题 No.33 排序链表