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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!