首页 > 其他分享 >环形链表II

环形链表II

时间:2022-12-13 11:32:12浏览次数:66  
标签:II head ListNode 环形 fast next 链表 null


题目地址(142. 环形链表 II)

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

题目描述

给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 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, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引



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

关键点

  • 详细解析见​​javascript:void(0)​​
  • 以及​​javascript:void(0)​​

代码

  • 语言支持:Java

Java Code:

/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
package com.wzc;

public class solution05 {
public ListNode detectCycle(ListNode head) {
ListNode inLoop = getNodeLoop(head);
if (inLoop == null){
return null;
}
int loopCount = 1;
// 统计环中节点个数
for (ListNode n = inLoop;n.next != inLoop;n = n.next){
loopCount++;
}
// 利用剑指offer21题的方法,查找倒数第loopCount个节点
ListNode fast = head;
for (int i =0;i<loopCount;i++){
fast = fast.next;
}
ListNode slow = head;
while (fast != slow){
slow = slow.next;
fast = fast.next;
}
return slow;
}

private ListNode getNodeLoop(ListNode head) {
if (head == null ||head.next == null){
return null;
}
ListNode fast = head.next;
ListNode slow = head;
while (slow !=null && fast !=null){
if (slow == fast){
return slow;
}
slow = slow.next;
fast = fast.next;
if (fast !=null){
fast = fast.next;
}
}
return null;
}
}

复杂度分析

令 n 为链表长度。

  • 时间复杂度:环形链表II_数据结构
  • 空间复杂度:环形链表II_空间复杂度_02


标签:II,head,ListNode,环形,fast,next,链表,null
From: https://blog.51cto.com/u_15911055/5933502

相关文章

  • 剑指Offer II 001.整数除法
    题目描述整数除法:给定两个整数a和b,求它们的除法的商a/b,要求不得使用乘号'*'、除号'/'以及求余符号'%' 。注意:整数除法的结果应当截去(truncate)其小数部分,例......
  • 脑筋急转弯-2498. 青蛙过河 II
    2498.青蛙过河IIDescriptionDifficulty:中等RelatedTopics:给你一个下标从0 开始的整数数组 stones ,数组中的元素 严格递增 ,表示一条河中石头的位置。一只......
  • BZOJ4536 : 最大异或和II
    建立$n+m$个点的无向图,其中$n$个点表示输入的数列,$m$个点表示答案的$m$个二进制位。对于输入的两个数$a[i],a[j]$,若它们存在公共二进制位,则可以通过同时选某一公共位来对......
  • python-miio 入门
    一、获取ip和tooken转载链接:https://github.com/PiotrMachowski/Xiaomi-cloud-tokens-extractor二、基础通信转载链接:https://github.com/rytilahti/python-miio/iss......
  • 剑指 Offer 56 - II. 数组中数字出现的次数 II(状态转移 位运算)
      ​​剑指Offer56-II.数组中数字出现的次数II​​难度中等38在一个数组 ​​nums​​ 中除一个数字只出现一次之外,其他数字都出现了三次。请找出那个只出现一次......
  • O(1)空间复杂度找到相交链表的交点
      相交链表编写一个程序,找到两个单链表相交的起始节点。如下面的两个链表:​​​​在节点c1开始相交。解题思路:首先将一条链首尾连起来,这时候就变成了找环的入口点的问题......
  • #yyds干货盘点# LeetCode程序员面试金典:链表相交
    题目:给你两个单链表的头节点 headA​ 和 headB​ ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null 。图示两个链表在节点 c1 开始相交:题目......
  • IIS 之 连接数、并发连接数、最大并发工作线程数、队列长度、最大工作进程数
    http://t.zoukankan.com/l1pe1-p-7742936.html一、IIS连接数一般购买过虚拟主机的朋友都熟悉购买时,会限制IIS连接数,顾名思义即为IIS服务器可以同时容纳客户请求的最......
  • IIS 6 下配置以 FastCGI 跑 PHP
    环境:操作系统:Windows2003ServerSP2PHP版本:php-5.2.6-Win321.下载FastCGIForIIS6http://www.iis.net/d...环境:操作系统:Windows200......
  • Nuxt.js IIS部署,Nuxt.js 发布部署vue-cli 安装 2020最新 vue 4.0安装
    第一步:服务器安装node.js环境1、安装node.js下载地址​​http://nodejs.cn/download/​​我是全部默认下一步的,安装成功之后运行命令查看是否安装成功如果没有出现版本号,......