算法记录lday3 LinkedList 链表移除 + 链表构建 + 链表反转reverse

news/2024/3/29 23:15:32/文章来源:https://blog.csdn.net/weixin_46969441/article/details/130378237

今日任务

● 链表理论基础
● 203.移除链表元素
● 707.设计链表
● 206.反转链表

链表理论基础

建议:了解一下链接基础,以及链表和数组的区别

文章链接:https://programmercarl.com/%E9%93%BE%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

203.移除链表元素

建议: 本题最关键是要理解 虚拟头结点的使用技巧,这个对链表题目很重要。

题目链接/文章讲解/视频讲解::https://programmercarl.com/0203.%E7%A7%BB%E9%99%A4%E9%93%BE%E8%A1%A8%E5%85%83%E7%B4%A0.html

707.设计链表

建议: 这是一道考察 链表综合操作的题目,不算容易,可以练一练 使用虚拟头结点

题目链接/文章讲解/视频讲解:https://programmercarl.com/0707.%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8.html

206.反转链表

建议先看我的视频讲解,视频讲解中对 反转链表需要注意的点讲的很清晰了,看完之后大家的疑惑基本都解决了。

题目链接/文章讲解/视频讲解:https://programmercarl.com/0206.%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8.html

DeleteNode链表 leetcode

链接

https://leetcode.com/problems/remove-linked-list-elements/

题目表示

Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.
在这里插入图片描述

思路

use one poiner cur to iterate thorough the whole linkedlist

whne the cur.val == val
remove this element

犯错点

处理头结点为目标值的情况,要用while循环处理
In the case of processing the head node as the target value,
it should be processed in a while loop.
处理完之后,判断head是否为空
After processing, determine if the head is empty
在循环删除 val 时,要使用一个pre变量表示 cur前的一个节点
When iteratively deleting val, use a pre variable to represent a node before cur

在处理 cur.val = val 时, prev.next = cur.next;
另外一种情况是, pre = cur; 更新 pre的位置

这两种情况都需要 移动 cur
cur = cur.next;

在这里插入图片描述

代码

class Solution {public ListNode removeElements(ListNode head, int val) {while (head != null && head.val == val) {head = head.next;}if(head == null) {return null;}ListNode pre = head;ListNode cur = head.next;while (cur != null) {if (cur.val == val) {pre.next = cur.next;} else {pre = cur;}cur = cur.next;}return head;}
}

思路简化

通过创建 一个dummyNode 在 head前面
避免对于 head.val == val的特殊情况的处理
By creating a dummyNode in front of the head
to Avoid handling special cases of head.val == val

class Solution {public ListNode removeElements(ListNode head, int val) {ListNode dummy = new ListNode(0);dummy.next = head;ListNode cur = dummy;while (cur != null && cur.next != null) {if (cur.next.val == val) {cur.next = cur.next.next;} else {cur = cur.next;}}return dummy.next;}
}

Design链表 leetcode 707

链接

https://leetcode.com/problems/design-linked-list/

题目描述

Design your implementation of the linked list. You can choose to use a singly or doubly linked list.
A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node.
If you want to use the doubly linked list, you will need one more attribute prev to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed.

Implement the MyLinkedList class:

MyLinkedList() Initializes the MyLinkedList object.
int get(int index) Get the value of the indexth node in the linked list. If the index is invalid, return -1.
void addAtHead(int val) Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
void addAtTail(int val) Append a node of value val as the last element of the linked list.
void addAtIndex(int index, int val) Add a node of value val before the indexth node in the linked list. If index equals the length of the linked list, the node will be appended to the end of the linked list. If index is greater than the length, the node will not be inserted.
void deleteAtIndex(int index) Delete the indexth node in the linked list, if the index is valid.

代码

class MyLinkedList {Node head;Node tail;int cap;public MyLinkedList() {this.head = new Node(-1);this.tail = new Node(-1);this.cap = 0;this.head.next = tail;this.tail.prev = head;}public Node getNode(int index) {Node cur = head.next;for (int i = 0; i < index; i++) {cur = cur.next;}return cur;}public int get(int index) {if(index < 0 || index >= cap) {return -1;}Node cur = getNode(index);return cur.val;}public void addAtHead(int val) {Node x = new Node(val);x.prev = this.head;x.next = head.next;head.next.prev = x;head.next = x;this.cap++;}public void addAtTail(int val) {Node x = new Node(val);x.prev = tail.prev;x.next = this.tail;tail.prev.next = x;tail.prev = x;this.cap++;}public void addAtIndex(int index, int val) {if (index > this.cap || index < 0) return;Node x = new Node(val);Node cur = getNode(index);Node p1 = cur.prev;Node p2 = cur;p1.next = x;p2.prev = x;x.prev = p1;x.next = p2;this.cap++;}public void deleteAtIndex(int index) {if (index >= this.cap || index < 0) return;Node cur = getNode(index);Node p1 = cur.prev;Node p2 = cur.next;p1.next = p2;p2.prev = p1;cur.next = cur.prev = null;this.cap--;}
}class Node{int val;Node prev;Node next;public Node(int val) {this.val = val;}
}/*** Your MyLinkedList object will be instantiated and called as such:* MyLinkedList obj = new MyLinkedList();* int param_1 = obj.get(index);* obj.addAtHead(val);* obj.addAtTail(val);* obj.addAtIndex(index,val);* obj.deleteAtIndex(index);*/

思路

设计一个linkedlist
Design a linkedlist
实现增删插改
Realize addition, deletion, insertion and modification

create Node class first
suggest use doubleNode
own three attribution
val
prev
next

create DoubleLinkedList
head
tail
size

don’t forget to update size,
when each time you implentent the insert, add, remove function

犯错点

对于get,insert, remove等方法
开始要进行index的检查
For get, insert, remove and other methods
need index check.

get 和 remove 检查 index是否 0 - size - 1内
Get and remove check whether the index is 0 - size - 1
insert 检查 index是否 0 - size内
Insert to check if the index is within 0- size
使用cur = head.next
for (i =0 ;i<index;i++ ) cur = cur.next;
就可以找到该节点位置

可以单独创建getNode方法使用
因为要经常使用这个
You can create the getNode method separately to use
Because we need to use this frequently

通过 getNode找到cur点之后

先处理 x 和 prev 和 cur关系

链表反转 Reverse LinkedList

思路

  1. consider the spcial case
  2. use two pointer

cur and prev to reverse the linkedlist

代码

指针

class Solution {public ListNode reverseList(ListNode head) {if (head == null || head.next == null) return head;ListNode cur = head, prev = null;while (cur != null) {ListNode next = cur.next;cur.next = prev;prev = cur;cur = next;}return prev;}
}

递归

这里定义的 reverseList
输入为 head
输出为 反转 head开头的链表

last = reverseList(head.next)
反转 head.next 开头的链表

head.next 是 head下一个指针
head.next.next = head 让head下一个指针指向 head
head.next = null 让head指向null节点

class Solution {public ListNode reverseList(ListNode head) {if (head == null || head.next == null) return head;ListNode last = reverseList(head.next);head.next.next = head;head.next = null;return last;}
}

指针变得递归

class Solution {public ListNode reverseList(ListNode head) {return reverse(null, head);}ListNode reverse(ListNode prev, ListNode cur) {if (cur == null) return prev;ListNode next = cur.next;cur.next = prev;return reverse(cur, next);}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_103870.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

JavaWeb搭建| Tomcat配置| Maven依赖|这一篇就够了(超详细)

&#x1f648;作者简介&#xff1a;练习时长两年半的Java up主 &#x1f649;个人主页&#xff1a;老茶icon &#x1f64a; ps:点赞&#x1f44d;是免费的&#xff0c;却可以让写博客的作者开兴好久好久&#x1f60e; &#x1f4da;系列专栏&#xff1a;Java全栈&#xff0c;计…

记录自己第一次项目管理(附件:WBS计划与会议纪要模板)

记录自己第一次项目管理 前言 20**年新入职到一家公司&#xff0c;刚到就接到紧急任务&#xff0c;因为上一个后端跑路&#xff0c;现在系统上出现接口报错、假接口的问题&#xff0c;客户又着急验收&#xff0c;所以入职之后&#xff0c;一直在着急改代码。最后因为系统没有…

思科模拟器 | 生成树协议STP、RSTP、HSRP配置

一、生成树协议STP 概念介绍&#xff1a; 生成树协议是一种网络协议&#xff0c;用于在交换机之间建立逻辑上的树形拓扑结构避免产生环路。为了完成这个功能&#xff0c;生成树协议需要进行些配置&#xff0c;包括根桥的选举、端口的状态切换等。 步骤明细&#xff1a; 使用思…

游戏测试的面试技巧

游戏测试的面试技巧 1.自我介绍 回答提示&#xff1a;一般人回答这个问题过于平常&#xff0c;只说姓名、年龄、爱好、工作经验 &#xff0c;这些在简历上都有&#xff0c;其实&#xff0c;企业最希望知道的是求职者能否胜任工作&#xff0c;包括&#xff1a;最强的技能、最深入…

实现PXE批量网络装机及kickstrat无人值守安装(富士山终究留不住欲落的樱花)

一、PXE概述和部署PXE批量装机 1.PXE简介 PXE&#xff08;预启动执行环境&#xff0c;在操作系统之前运行&#xff09;是由Intel公司开发的网络引导技术&#xff0c;c/s架构&#xff0c;允许客户机通过网络从远程服务器下载引导镜像&#xff0c;并加载安装文件或者整个操作系统…

燃气管道定位83KHZ地下电子标识器探测仪ED-8000操作指南

1、电子标识器探测工作 燃气管道定位83KHZ地下电子标识器探测仪ED-8000&#xff0c;探测时周边 3 米范围内不能有其他探测仪&#xff0c;保持探测仪垂直向 下&#xff0c;探测仪的末端距离地面 5~10cm 左右&#xff0c;延估计的埋地管线走向水平移动探测仪。当发现持续信号且信…

RuntimeError: “LayerNormKernelImpl“ not implemented for ‘Long‘解决方法

问题出现的场景&#xff1a; 输入&#xff1a; import torch import torch.nn as nn atorch.randint(10,[3,4]) # atorch.DoubleTensor(a) # aa.double() print(a) layer_normnn.LayerNorm(4) layer_norm(a) 我就是想测试一下经过layernorm之后的输出会变成什么样 但是报错…

量表题如何分析?

量表是一种测量工具&#xff0c;量表设计标准有很多&#xff0c;并且每种量表的设计都有各自的特性&#xff0c;不同量表的特性也决定了测量尺度&#xff0c;在数据分析中常用的量表为李克特量表。李克特量表1932年由美国社会心理学家李克特在当时原有总加量表的基础上进行改进…

eBPF的发展演进---从石器时代到成为神(二)

3. 发展溯源 回顾技术的发展过程&#xff0c;就像观看非洲大草原日出日落一样&#xff0c;宏大的过程让人感动&#xff0c;细节部分引人深思。每天循环不辍&#xff0c;却又每天不同。 BPF的应用早已超越了它最初的设计&#xff0c;但如果要追溯BPF最初的来源&#xff0c;则必…

kubernetes为何需要默认的serviceaccount?

文章目录 什么是k8s的serviceAccount&#xff1f;为什么每一个ns下都有默认的sa&#xff1f;default sa yaml 默认的sa下都会挂一个secret&#xff0c;这个secret是从哪里来的&#xff1f;一道关于RBAC的CKA考题1、创建一个新的 ServiceAccount2、创建一个新的 Role3、创建一个…

2023_8.0.33版windows版MySql安装_配置远程连接_修改设置初始密码---MySql工作笔记0001

MySQL :: Download MySQL Community Server https://dev.mysql.com/downloads/mysql/ 首先去下载mysql 可以看到这里下载第一个就可以了,最新版的8.0.33 这里点击仅仅下载 just start my download 然后解压到一个文件夹,然后配置一下环境变量 然后新建一个my.ini文件 然后把…

【GNN】谱域图卷积

谱域图卷积 1. 谱域卷积的背景知识 1.1 谱域图卷积实现思路 f 1 ( t ) ⋆ f 2 ( t ) F − 1 [ F 1 ( w ) F 2 ( w ) ] f_1(t) \star f_2(t) F^{-1}[F_1(w)F_2(w) ] f1​(t)⋆f2​(t)F−1[F1​(w)F2​(w)] 1.2 如何定义图上的傅里叶变换 经典傅里叶变换&#xff1a; x ( …

速卖通正式推出全托管,卖家竞争进入新阶段

全托管来了&#xff0c;卖家就能安心做甩手掌柜吗&#xff1f; 正式推出全托管 显而易见&#xff0c;越来越多的平台正在转向全托管模式。 近日&#xff0c;速卖通在2023年度商家峰会上&#xff0c;正式推出了全托管服务模式。官方表示&#xff0c;托管是对速卖通平台商家服…

golang微服务项目通用流水线

golang微服务项目通用流水线 工作中随着业务越来越大&#xff0c;微服务的项目也越来越多&#xff0c;最开始的时候是一个服务一个流水线&#xff0c;然后还分了三个环境&#xff0c;也就是一个服务三个流水线&#xff0c;后面就越来越不利于管理维护了&#xff0c;因此&#…

持续集成——App自动化测试集成实战

这里写目录标题 一、app自动化测试持续集成的好处二、环境准备三、Jenkins节点挂载四、节点环境的配置1、JDK2、模拟器3、sdk环境4、Python3环境5、allure-commandline工具6、allure插件 五、本地运行待测代码(保证代码没有问题)六、库文件的导出七、Jenkins上运行代码配置1、指…

Visual Studio C# WinForm开发入门(4):概述

目录 一.Winform入门1.WinForm项目结构2.窗口设计与控件布局3.窗口事件4.时间显示器小练习 二.WinForm布局开发1.手动布局解决自适应问题2.WinForm布局属性3.WinForm布局器 三.WinForm常用控件1.界面展示2.实体类 Student(封装信息)3.逻辑事件代码Form.cs 四.图片框与项目资源1…

智慧班牌源码,使用springboot框架Java+vue2开发,二次开发方便快捷

智慧校园云平台电子班牌系统源码 智慧校园平台电子班牌系统源码在大数据平台下&#xff0c;对应用系统进行统一&#xff0c;以数据互联软硬结合的特点应用在校园&#xff0c;实现对校园、班级、教师、学生的管理。 智慧校园云平台电子班牌系统源码&#xff0c;使用springboot…

【视频课程】算法工程师需要的ChatGPT大模型算法理论与实践课程!非粗浅科普...

前言 自从2022年11月ChatGPT发布之后&#xff0c;迅速火遍全球。其对话的交互方式&#xff0c;能够回答问题&#xff0c;承认错误&#xff0c;拒绝不适当的请求&#xff0c;高质量的回答&#xff0c;极度贴近人的思维的交流方式&#xff0c;让大家直呼上瘾&#xff0c;更是带火…

软件开发全套文档案例分享

写在前面 在日常项目开发过程中&#xff0c;会产生大量的过程文档&#xff0c;比如开发过程中的文档、管理过程中的文档、产品相关文档等等&#xff0c;那这些文档我们日常怎么去管理呢&#xff1f;怎么去做规划呢&#xff1f;如何做成通用标准呢&#xff1f;小编特地整理了一…

5款超实用电脑办公软件推荐

1.AIDA64 AIDA64是一款电脑软硬件检测工具&#xff0c;它不仅可以详细的显示出PC的每一个方面的信息&#xff0c;还提供了诸如协助超频&#xff0c;硬件侦错&#xff0c;压力测试和传感器监测等多种功能&#xff0c;以帮助我们对电脑整体性能进行全面评估。 2.傲梅分区助手 …