[链表专题]力扣206, 203, 19

2024-05-07 20:44
文章标签 链表 力扣 206 19 专题 203

本文主要是介绍[链表专题]力扣206, 203, 19,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1. 力扣206 : 反转链表

(1). 题 : 图略

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。示例 1:输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]
示例 2:输入:head = [1,2]
输出:[2,1]
示例 3:输入:head = []
输出:[]提示:链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

解法1 : 

该解法的空间复杂度比较高(O(n)), 因为借助了int[n]大小的数组.但空间换时间, 该解法的时间复杂度较低(O(n)).只有for一层循环.

思路 : 首先遍历链表,得到链表节点的个数,借助数组存储原链表的节点的数据域,再for循环覆盖原链表的节点的数据域.

解 : 

class Solution {public ListNode reverseList(ListNode head) {ListNode p;int count = 0;for (p = head; p != null; p = p.next) {count++;}int newCount = count;int[] arr = new int[count];count = 0;for (p = head; p != null; p = p.next) {arr[count++] = p.val;   }count = 0;for (p = head; p != null; p = p.next) {p.val = arr[newCount - 1];newCount--;}return head;}
}

解法2 : 可以使用递归来解决.以示例1为例.

思路 : 不断递归, 当递归到head指向节点5时(最后一个节点), 返回节点5, last指向节点5, 此时head指向节点4, 将节点5指向节点4, 节点4的指针域设置为null, 返回last指针.

解 : 

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;}
}

解法3 : 迭代+双指针

思路 : n1初始时指向空,o1记录头节点的下一个节点,不断将原链表的节点头插到空链表中,并更新n1使得其指向该链表的头节点.

解法 : 

class Solution {public ListNode reverseList(ListNode head) {if (head == null) {return head;}ListNode n1 = null;while (head != null) {ListNode o1 = head.next;head.next = n1;n1 = head;head = o1;}return n1;}
}

2. 力扣203 : 移除链表元素

题 : 图略

给你一个链表的头节点 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
输出:[]提示:列表中的节点数目在范围 [0, 104] 内
1 <= Node.val <= 50
0 <= val <= 50

解法1 : 迭代

思路 : 增加哨兵节点, 使得处理头节点变得简单.想要删除一个节点, 得找到想要删除节点的上一个节点, 从哨兵节点开始, 如果其下一个节点的数据域为val, 则删除, 否则将指针移到下一个节点.

解 : 

class Solution {public ListNode removeElements(ListNode head, int val) {//增加头节点if (head == null) {return null;} //哨兵节点ListNode dummy = new ListNode(0);dummy.next = head;ListNode temp = dummy;while (temp.next != null) {if (temp.next.val == val) {temp.next = temp.next.next;} else {temp = temp.next;}}return dummy.next;}
}

解法2 : 递归

思路 : 基线条件,如果head为null,则返回null.如果我(当前head所在节点)的数据域与val相等,则返回我的下一个节点的递归结果.如果我的数据域与val不想等,则返回我与我的下一个节点的递归结果.

解 : 

class Solution {public ListNode removeElements(ListNode head, int val) {if (head == null) {return head;}//如果我与val相等, 返回下一个节点的递归结果if (head.val == val) {return removeElements(head.next, val);} else {//如果我与val不相等, 则返回我以及我的下一个节点的递归结果head.next = removeElements(head.next, val);return head;}}
}

3. 力扣19 : 删除链表的倒数第n个节点

题 : 

给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。示例 1:输入:head = [1,2,3,4,5], n = 2
输出:[1,2,3,5]
示例 2:输入:head = [1], n = 1
输出:[]
示例 3:输入:head = [1,2], n = 1
输出:[1]提示:链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz进阶:你能尝试使用一趟扫描实现吗?

解法1 : 双指针(快慢指针)

注 : 题目中n是合法的, 所以无需考虑n不合法的情况.

思路 : 设置哨兵节点, 为了方便删除头节点的操作.初始时, 快慢指针均指向哨兵节点, fast指针先动,然后快慢指针一起移动, 当fast指针指向最后一个节点时, slow指针刚好指针待删除节点的上一个节点.

解 : 

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {//设置哨兵节点ListNode dummy = new ListNode(0);dummy.next = head;ListNode fast = dummy;ListNode slow = dummy;while (n-- > 0) {fast = fast.next;}while (fast.next != null) {fast = fast.next;slow = slow.next;}slow.next = slow.next.next;return dummy.next;}
}

这篇关于[链表专题]力扣206, 203, 19的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

【专题】2024飞行汽车技术全景报告合集PDF分享(附原数据表)

原文链接: https://tecdat.cn/?p=37628 6月16日,小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞,这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示,公司准备量产,并计划今年四季度开启预售小鹏汇天分体式飞行汽车,探索分体式飞行汽车城际通勤。阅读原文,获取专题报告合集全文,解锁文末271份飞行汽车相关行业研究报告。 据悉,业内人士对飞行汽车行业

csu1329(双向链表)

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

深入手撕链表

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

建立升序链表

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

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

音视频入门基础:WAV专题(10)——FFmpeg源码中计算WAV音频文件每个packet的pts、dts的实现

一、引言 从文章《音视频入门基础:WAV专题(6)——通过FFprobe显示WAV音频文件每个数据包的信息》中我们可以知道,通过FFprobe命令可以打印WAV音频文件每个packet(也称为数据包或多媒体包)的信息,这些信息包含该packet的pts、dts: 打印出来的“pts”实际是AVPacket结构体中的成员变量pts,是以AVStream->time_base为单位的显

学习记录:js算法(二十八):删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一:循环解法二:递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1:(图一)输入:head = [1,1,2]输出:[1,2]示例 2:(图

两数之和--力扣1

两数之和 题目思路C++代码 题目 思路 根据题目要求,元素不能重复且不需要排序,我们这里使用哈希表unordered_map。注意题目说了只对应一种答案。 所以我们在循环中,使用目标值减去当前循环的nums[i],得到差值,如果我们在map中能够找到这个差值,就说明存在两个整数的和为目标值。 如果没有找到,就将当前循环的nums[i]以及下标i放入map中,以便后续查

专题二_滑动窗口_算法专题详细总结

目录 滑动窗口,引入: 滑动窗口,本质:就是同向双指针; 1.⻓度最⼩的⼦数组(medium) 1.解析:给我们一个数组nums,要我们找出最小子数组的和==target,首先想到的就是暴力解法 1)暴力: 2)优化,滑动窗口: 1.进窗口 2.出窗口 3.更新值 2.⽆重复字符的最⻓⼦串(medium) 1)仍然是暴力解法: 2)优化: 进窗口:hash[s[rig

力扣第347题 前K个高频元素

前言 记录一下刷题历程 力扣第347题 前K个高频元素 前K个高频元素 原题目: 分析 我们首先使用哈希表来统计数字出现的频率,然后我们使用一个桶排序。我们首先定义一个长度为n+1的数组,对于下图这个示例就是长度为7的数组。为什么需要一个长度为n+1的数组呢?假如说总共有三个数字都为1,那么我们需要把这个1放在数组下标为3的位置,假如说数组长度为n,对于这个例子就是长度为3,那么它的