Day3-链表第一部分|LeetCode203、707、206|代码随想录

2023-10-29 19:12

本文主要是介绍Day3-链表第一部分|LeetCode203、707、206|代码随想录,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

今天开始写链表的题目。链表的核心内容是需要了解它的一些基础是如何实现的,在此基础上做的延伸一般不会太复杂。


LeetCode 203 题目描述+解答

解题思路:移除链表中的元素,这里引入一个虚拟的头指针来统一操作。难度不大,主要是java基础不太好,自己写测试用例的时候耽误了很久。这里的判断,需要if else 本来写的时候没有带else,直接写的 cur=cur.next; 想着删除完了也得移动cur,就直接写了,但是这样会报错。因为如果当前val是对应到链表的最后一个元素,那我们的cur此时已经指向了null,下面如果再有一个cur=cur.next;语句,就会报错。所以这里要放在else中。

Java代码:

import org.joni.ast.ListNode;/*** 题目Id:203; * 题目:移除链表元素,remove-linked-list-elements; * 日期:2023-10-29 15:05:20
*///给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。// 示例 1: 
//输入:head = [1,2,6,3,4,5,6], val = 6
//输出:[1,2,3,4,5]
// 
// 示例 2: 
//输入:head = [], val = 1
//输出:[]
// 
// 示例 3: 
//输入:head = [7,7,7,7], val = 7
//输出:[]/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/class Solution {public ListNode removeElements(ListNode head, int val) {if (head == null) {return head;}ListNode dummy = new ListNode(-1,head);ListNode cur = dummy;while (cur.next != null){if (cur.next.val == val){cur.next=cur.next.next;}else{cur=cur.next;}}return dummy.next;}
}}

LeetCode 707 题目描述+解答

解题思路:这道题目有很多链表中涉及到的操作。是很基础且必须的题目。我写的太乱了,这里直接用网站上的代码做示例,有一个地方需要注意,就是链表中的size属性。

Java代码:

import com.github.weisj.jsvg.L;
import com.vladsch.flexmark.ast.LinkNode;
import com.vladsch.flexmark.util.sequence.BasedSequence;
import org.jetbrains.annotations.NotNull;/*** 题目Id:707; * 题目:设计链表,design-linked-list; * 日期:2023-10-29 16:00:04
*///你可以选择使用单链表或者双链表,设计并实现自己的链表。 单链表中的节点应该具备两个属性:val 和 next 。val 是当前节点的值,next 是指向下一个节点的指针/引用。如果是双向链表,则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。 // 实现 MyLinkedList 类: 
// MyLinkedList() 初始化 MyLinkedList 对象。 
// int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效,则返回 -1 。 
// void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后,新节点会成为链表的第一个节点。 
// void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。 
// void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 
//index 等于链表的长度,那么该节点会被追加到链表的末尾。如果 index 比长度更大,该节点将 不会插入 到链表中。 
// void deleteAtIndex(int index) 如果下标有效,则删除链表中下标为 index 的节点。 // 示例: 
//输入
//["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", 
//"deleteAtIndex", "get"]
//[[], [1], [3], [1, 2], [1], [1], [1]]
//输出
//[null, null, null, null, 2, null, 3]
//
//解释
//MyLinkedList myLinkedList = new MyLinkedList();
//myLinkedList.addAtHead(1);
//myLinkedList.addAtTail(3);
//myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3
//myLinkedList.get(1);              // 返回 2
//myLinkedList.deleteAtIndex(1);    // 现在,链表变为 1->3
//myLinkedList.get(1);              // 返回 3//单链表
class ListNode {int val;ListNode next;ListNode(){}ListNode(int val) {this.val=val;}
}
class MyLinkedList {//size存储链表元素的个数int size;//虚拟头结点ListNode head;//初始化链表public MyLinkedList() {size = 0;head = new ListNode(0);}//获取第index个节点的数值,注意index是从0开始的,第0个节点就是头结点public int get(int index) {//如果index非法,返回-1if (index < 0 || index >= size) {return -1;}ListNode currentNode = head;//包含一个虚拟头节点,所以查找第 index+1 个节点for (int i = 0; i <= index; i++) {currentNode = currentNode.next;}return currentNode.val;}//在链表最前面插入一个节点,等价于在第0个元素前添加public void addAtHead(int val) {addAtIndex(0, val);}//在链表的最后插入一个节点,等价于在(末尾+1)个元素前添加public void addAtTail(int val) {addAtIndex(size, val);}// 在第 index 个节点之前插入一个新节点,例如index为0,那么新插入的节点为链表的新头节点。// 如果 index 等于链表的长度,则说明是新插入的节点为链表的尾结点// 如果 index 大于链表的长度,则返回空public void addAtIndex(int index, int val) {if (index > size) {return;}if (index < 0) {index = 0;}size++;//找到要插入节点的前驱ListNode pred = head;for (int i = 0; i < index; i++) {pred = pred.next;}ListNode toAdd = new ListNode(val);toAdd.next = pred.next;pred.next = toAdd;}//删除第index个节点public void deleteAtIndex(int index) {if (index < 0 || index >= size) {return;}size--;if (index == 0) {head = head.next;return;}ListNode pred = head;for (int i = 0; i < index ; i++) {pred = pred.next;}pred.next = pred.next.next;}
}//双链表
class ListNode{int val;ListNode next,prev;ListNode() {};ListNode(int val){this.val = val;}
}class MyLinkedList {  //记录链表中元素的数量int size;//记录链表的虚拟头结点和尾结点ListNode head,tail;public MyLinkedList() {//初始化操作this.size = 0;this.head = new ListNode(0);this.tail = new ListNode(0);//这一步非常关键,否则在加入头结点的操作中会出现null.next的错误!!!head.next=tail;tail.prev=head;}public int get(int index) {//判断index是否有效if(index<0 || index>=size){return -1;}ListNode cur = this.head;//判断是哪一边遍历时间更短if(index >= size / 2){//tail开始cur = tail;for(int i=0; i< size-index; i++){cur = cur.prev;}}else{for(int i=0; i<= index; i++){cur = cur.next; }}return cur.val;}public void addAtHead(int val) {//等价于在第0个元素前添加addAtIndex(0,val);}public void addAtTail(int val) {//等价于在最后一个元素(null)前添加addAtIndex(size,val);}public void addAtIndex(int index, int val) {//index大于链表长度if(index>size){return;}//index小于0if(index<0){index = 0;}size++;//找到前驱ListNode pre = this.head;for(int i=0; i<index; i++){pre = pre.next;}//新建结点ListNode newNode = new ListNode(val);newNode.next = pre.next;pre.next.prev = newNode;newNode.prev = pre;pre.next = newNode;}public void deleteAtIndex(int index) {//判断索引是否有效if(index<0 || index>=size){return;}//删除操作size--;ListNode pre = this.head;for(int i=0; i<index; i++){pre = pre.next;}pre.next.next.prev = pre;pre.next = pre.next.next;}
}/*** 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);*/

LeetCode 206 题目描述+解答

解题思路:链表反转问题。常规思路:利用双指针,只需要将现有链表的指针方向全部反过来就行了。递归思路:根据常规写法递归即可。

Java代码:

import org.joni.ast.ListNode;/*** 题目Id:206; * 题目:反转链表,reverse-linked-list; * 日期:2023-10-29 16:56:24
*///给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
// 示例 1: 
//输入:head = [1,2,3,4,5]
//输出:[5,4,3,2,1]
// 
// 示例 2: 
//输入:head = [1,2]
//输出:[2,1]
// 
// 示例 3: 
//输入:head = []
//输出:[]/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*///常规逆转思路
class Solution {public ListNode reverseList(ListNode head) {ListNode pre = null;ListNode cur = head;ListNode temp = new ListNode();while (cur != null){temp = cur.next;cur.next = pre;pre=cur;cur=temp;}return pre;}    
}
}//递归思路
class Solution {public ListNode reverse(ListNode cur,ListNode pre){ListNode temp = new ListNode();if (cur == null) return pre;//反转操作 递归的核心是抽象出来统一的操作,然后传不同的参数进去,找到核心操作步骤之后,理清楚要传的参数就能得到结果。temp = cur.next;cur.next = pre;return reverse(temp,cur);}public ListNode reverseList(ListNode head) {return reverse(head,null);}
}

这篇关于Day3-链表第一部分|LeetCode203、707、206|代码随想录的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/302778

相关文章

csu1329(双向链表)

题意:给n个盒子,编号为1到n,四个操作:1、将x盒子移到y的左边;2、将x盒子移到y的右边;3、交换x和y盒子的位置;4、将所有的盒子反过来放。 思路分析:用双向链表解决。每个操作的时间复杂度为O(1),用数组来模拟链表,下面的代码是参考刘老师的标程写的。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#

活用c4d官方开发文档查询代码

当你问AI助手比如豆包,如何用python禁止掉xpresso标签时候,它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能

深入手撕链表

链表 分类概念单链表增尾插头插插入 删尾删头删删除 查完整实现带头不带头 双向链表初始化增尾插头插插入 删查完整代码 数组 分类 #mermaid-svg-qKD178fTiiaYeKjl {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-

代码随想录冲冲冲 Day39 动态规划Part7

198. 打家劫舍 dp数组的意义是在第i位的时候偷的最大钱数是多少 如果nums的size为0 总价值当然就是0 如果nums的size为1 总价值是nums[0] 遍历顺序就是从小到大遍历 之后是递推公式 对于dp[i]的最大价值来说有两种可能 1.偷第i个 那么最大价值就是dp[i-2]+nums[i] 2.不偷第i个 那么价值就是dp[i-1] 之后取这两个的最大值就是d

pip-tools:打造可重复、可控的 Python 开发环境,解决依赖关系,让代码更稳定

在 Python 开发中,管理依赖关系是一项繁琐且容易出错的任务。手动更新依赖版本、处理冲突、确保一致性等等,都可能让开发者感到头疼。而 pip-tools 为开发者提供了一套稳定可靠的解决方案。 什么是 pip-tools? pip-tools 是一组命令行工具,旨在简化 Python 依赖关系的管理,确保项目环境的稳定性和可重复性。它主要包含两个核心工具:pip-compile 和 pip

建立升序链表

题目1181:遍历链表 时间限制:1 秒 内存限制:32 兆 特殊判题:否 提交:2744 解决:1186 题目描述: 建立一个升序链表并遍历输出。 输入: 输入的每个案例中第一行包括1个整数:n(1<=n<=1000),接下来的一行包括n个整数。 输出: 可能有多组测试数据,对于每组数据, 将n个整数建立升序链表,之后遍历链表并输出。 样例输

D4代码AC集

贪心问题解决的步骤: (局部贪心能导致全局贪心)    1.确定贪心策略    2.验证贪心策略是否正确 排队接水 #include<bits/stdc++.h>using namespace std;int main(){int w,n,a[32000];cin>>w>>n;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+n+1);int i=1