首页 > 其他分享 >力扣141-环形链表

力扣141-环形链表

时间:2023-12-16 17:24:08浏览次数:29  
标签:力扣 141 一个 链表 步长 移动 节点 指针

难度:【简单】

第一遍:用最朴素的算法写,一个HashSet保存访问过的节点,但是仅保存了节点的value,出现值相等的节点算法就会失效。提交后当然是“解答错误”。

第二遍:修改HashSet数据类型,重新提交后显示“通过”。

第三遍:优化空间复杂度到O(1)。没有思路就参考了官方题解,使用了快慢指针。自己写的时候,想当然的认为“一个指针在前一个指针在后罢了”,运行一下报错“超时”。改了一下快指针的步长,运行结果才对了。为什么两个指针一个每次移动一步,一个每次移动两步呢?可以预设一下两个指针移动步长相等的情况:一前一后,两个指针的距离始终不变,即使有环两个指针也无法相遇,循环无法终止。只有“一个移动得快,一个移动得慢”,两个指针才有可能相遇,这才是所谓的“快慢指针”,一个跑得快一个跑得慢。

标签:力扣,141,一个,链表,步长,移动,节点,指针
From: https://www.cnblogs.com/metasequoiaa/p/17905062.html

相关文章

  • P1416 攻击火星
    思路:需要构造出一种最优解情况这样就最多能删去2个#include<bits/stdc++.h>usingnamespacestd;voidsolve(){ intn; cin>>n; intans=max(0,n-2); cout<<ans;}intmain(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); intt=1; //cin>>t; for(i......
  • 2023-2024-1 20231419 《计算机基础与程序设计》第十二周学习总结
    2023-2024-120231419《计算机基础与程序设计》第十二周学习总结作业信息这个作业属于哪个课程https://edu.cnblogs.com/campus/besti/2023-2024-1-CFAP这个作业要求在哪里https://www.cnblogs.com/rocedu/p/9577842.html#WEEK12这个作业的目标自学《C语言程序设......
  • 代码随想录算法训练营第三天|203.移除链表元素、707.设计链表、206.反转链表
    LeetCode 203.移除链表元素题目链接:203.移除链表元素原链表删除元素(需要区分头节点和非头结点)使用虚拟头节点,统一链表操作(注意:新链表头结点是虚拟头节点的下一节点) LetCode707.设计链表题目链接:707.设计链表注意:头节点采用虚拟头节点,使得链表操作具有一致性!!!单链......
  • 算法学习Day3虚拟头指针,设计链表,反转链表
    Day3虚拟头指针,设计链表,反转链表ByHQWQF2023/12/15笔记203.移除链表元素给你一个链表的头节点head和一个整数val,请你删除链表中所有满足Node.val==val的节点,并返回新的头节点。解法:虚拟头指针看起来非常简单,但是由于如果直接对原始的链表进行操作,如果头节点的v......
  • 代码随想录算法训练营第三天 | 链表理论基础,203.移除链表元素,707.设计链表,206.反转链
    一、链表理论基础学习:1.链表定义线性表的一种存储方式,在逻辑上连续的数据在物理存储中可以不连续。classListNode{intval;ListNodenext;ListNode(){}ListNode(intval){this.val=val;this.next=null;}ListN......
  • 代码随想录算法训练营Day3 | 203.移除链表元素、707.设计链表、206.翻转链表
    这三道题都不涉及什么难以理解的算法,是对链表基础知识的一个复习巩固对于有数据结构基础的同学来说这个没有什么难度但是,写代码的过程中,我明显感觉到,我需要更加完善和统一的代码风格,作为一个前OIer,我的c和cpp混用的情况在基础数据结构的封装层面造成了不小的混乱!我需要去补充c......
  • 206. 反转链表
    题目206.反转链表要求给你单链表的头节点head,请你反转链表,并返回反转后的链表。答案这道题目也是使用虚拟节点,我先使用虚拟节点做了一遍,结果如下,就是想清楚在循环的时候保留当前节点就可以:publicstaticListNodereverseList(ListNodehead){ListNodevirtual=n......
  • 707. 设计链表
    题目:707.设计链表要求:你可以选择使用单链表或者双链表,设计并实现自己的链表。单链表中的节点应该具备两个属性:val 和 next 。val 是当前节点的值,next 是指向下一个节点的指针/引用。如果是双向链表,则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点......
  • 203. 移除链表元素
    题目:203.移除链表元素要求:给你一个链表的头节点head和一个整数val,请你删除链表中所有满足Node.val==val的节点,并返回新的头节点。解答:独自写出来了,但是代码=写的不好,我的思路是分两步,第一步先把头节点等于目标值的节点全部删除,第二步在遍历后续节点,删除等于目标值......
  • 【删除排序链表中的重复元素】模拟
    leetcode82.删除排序链表中的重复元素II题意:只要链表中元素x重复出现了,删除所有元素x(刚开始还读错题了……)题解:在表头前添加链表的虚拟节点dummy遍历链表(1)如果当前节点cur的下一个节点cur.next和cur.next.next相等,则意味着出现了重复元素,记录元素值,从cur.next开始挨个删......