Leetcode的AC指南 —— 链表:142.环形链表II

2023-12-21 00:46:53

摘要:
Leetcode的AC指南 —— 链表:142.环形链表II。题目介绍:给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

一、题目


力扣题目链接

题目介绍:给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1:
在这里插入图片描述

输入:head = [3,2,0,-4], pos = 1
输出:返回索引为 1 的链表节点
解释:链表中有一个环,其尾部连接到第二个节点。

示例 2:
在这里插入图片描述

输入:head = [1,2], pos = 0
输出:返回索引为 0 的链表节点
解释:链表中有一个环,其尾部连接到第一个节点。

示例3:
在这里插入图片描述

输入:head = [1], pos = -1
输出:返回 null
解释:链表中没有环。

提示:
链表中节点的数目范围在范围 [0, e4] 内
-e5 <= Node.val <= e5
pos 的值为 -1 或者链表中的一个有效索引

进阶:

  • 你是否可以使用 O(1) 空间解决此题?

二、解析


1、快慢指针法

思路:

// 快慢指针
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        // fast指针每次走两个节点,slow指针每次走一个节点,有环的话必相遇, 追击问题
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){ // 有环
                ListNode index1 = fast; // 指向相遇的节点
                ListNode index2 = head; // 指向头节点
                // 头节点到入环点的长度 = x,环的长度 = y + z(以相遇点划分,从入环点到相遇点为y,从入环点到相遇点为z)
                // 则fast走过的路程是slow的2倍, 2 *(x + y)= x + y + n *(y + z),n为fast走了n圈。
                // 化简, x = z + (n - 1)*(y + z)
                // 表示,两个指针分别从头节点和相遇点出发,各走一步,一定会在入环点相遇。
                // 至于slow的长度为什么是 x + y 而不是 x + n *(y + z)+ y。
                // 这是因为slow走到入环点时,fast一定在环中的某一个位置,之后slow和fast的每次移动,都表示slow和fast之间的距离减1。
                // 而slow和fast的距离最大也就是环的长度y + z,也就表示,slow和fast相遇时,slow走不完环的一周。
                while(index2 != index1){
                    index2 = index2.next;
                    index1 = index1.next;
                }

                return index1;
            }
        }
        return null;
    }
  • 时间复杂度: O(n),快慢指针相遇前,指针走的次数小于链表长度,快慢指针相遇后,两个index指针走的次数也小于链表长度,总体为走的次数小于 2n
  • 空间复杂度: O(1)

2、一个破坏链表的解法

  public ListNode detectCycle(ListNode head) {
  		// 若头节点为null或者链表只有一个节点,直接返回null
        if(head == null) return null;
        if(head.next == null) return null;
        ListNode pre = head;
        ListNode cur = head.next;
        // 若当前节点不是目标节点,则从链表中删除,目标节点一定是遍历链表的最后一个节点
        while (cur != null){
            pre.next = null;
            pre = cur;
            cur = pre.next;
        }
        return pre;
    }

3、 一个超时的题解

思路:
判断当前节点的下一个节点在没在当前节点前面的节点序列中,在就返回当前节点的下一个节点,否则就让当前接节点等于他的下一个节点

public ListNode detectCycle(ListNode head) {
        if(head == null) return null;
        ListNode cur = head;
        ListNode result = head;
        if (result == cur.next) return result;
        while (cur != null){
            while (cur != result) {
                if (result == cur.next) return result;
                result = result.next;
            }
            cur = cur.next;
            result = head;
        }
        return null;
    }
  • 时间复杂度O(n2)
  • 空间复杂度O(1)

文章来源:https://blog.csdn.net/Huacyu/article/details/135047556
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。