算法打卡day3|链表篇|Leetcode 203.移除链表元素、 707.设计链表 、 206.反转链表

2024-02-27 09:12

本文主要是介绍算法打卡day3|链表篇|Leetcode 203.移除链表元素、 707.设计链表 、 206.反转链表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

链表基本概念

定义

链表是一种通过指针串联在一起的线性结构,每一个节点由两部分组成,一个是数据域一个是指针域(存放指向下一个节点的指针),最后一个节点的指针域指向null(空指针的意思)。其中链表的入口节点称为链表的头节点也就是head

以下是java构造的链表结构,注意在力扣中,链表底层代码构造好的可以直接引用。

public class ListNode {// 节点的值int val;// 下一个节点ListNode next;// 节点的构造函数(无参)public ListNode() {}// 节点的构造函数(有一个参数)public ListNode(int val) {this.val = val;}// 节点的构造函数(有两个参数)public ListNode(int val, ListNode next) {this.val = val;this.next = next;}
}

链表的类型

接下来说一下链表的几种类型:

单链表

单链表中的指针域只能指向节点的下一个节点。

双链表

双链表:每一个节点有两个指针域,一个指向下一个节点,一个指向上一个节点。所以既可以向前查询也可以向后查询

链表2

循环链表

循环链表,链表首尾相连。可以用来解决约瑟夫环问题。

链表4

链表的存储方式

数组是在内存中是连续分布的,但是链表在内存中可不是连续分布的。

链表是通过指针域的指针链接在内存中各个节点。(相当于若干个抽屉,抽屉里放着开启下一个抽屉的钥匙,这些抽屉可以随机摆放

链表中的节点在内存中不是连续分布的 ,而是散乱分布在内存中的某地址上,分配机制取决于操作系统的内存管理。

链表的操作

删除节点

链表-删除节点

若要删除D节点,只要将C节点的next指针 指向E节点就可以了。D虽然还存在但Java自身有内存回收机制,就不用手动释放。

添加节点

链表-添加节点

将C的指针指向F,F的指针指向D即完成添加

性能对比分析

链表的特性和数组的特性进行一个对比,如图所示:

链表-链表与数据性能对比

数组在定义的时候,长度就是固定的,如果想改动数组的长度,就需要重新定义一个新的数组。

链表的长度可以是不固定的,并且可以动态增删, 适合数据量不固定,频繁增删,较少查询的场景。

算法题

Leetcode  203.移除链表元素

题目链接:203.移除链表元素

大佬视频讲解:移除链表元素讲解视频

个人思路

使用虚拟头节点,遍历链表,找到值就删除。

解法

原表删除

直接使用原来的链表来进行删除操作但移除头节点和移除其他节点的操作是不一样的,因为链表的其他节点都是通过前一个节点来移除当前节点,而头节点没有前一个节点

所以删除头节点,只要将头节点向后移动一位就可以移除头节点。

class Solution {public ListNode removeElements(ListNode head, int val) {while (head != null && head.val == val) {//若头节点值相同则删除head = head.next;}if (head == null) {return head;}ListNode pre = head;// 已确定当前head.val != valListNode cur = head.next;while (cur != null) {if (cur.val == val) {pre.next = cur.next;//删除元素} else {pre = cur;}cur = cur.next;}return head;
}
}

时间复杂度:O( n);(两个while循环,2*n)

空间复杂度:O(1);(没有使用多余空间)

伪头节点删除

设置一个虚拟头节点在进行删除操作,这样不用单独考虑头节点是否需要删除的情况;这是以后处理链表的主流方法.

class Solution {public ListNode removeElements(ListNode head, int val) {if (head == null) {return head;}//定义相当于 ListNode dummy=new ListNode(0); dummy.next=head;ListNode dummy = new ListNode(-1, head);//伪头节点ListNode pre = dummy;//上一个节点ListNode cur = head;//当前节点while (cur != null) {if (cur.val == val) {pre.next = cur.next;//删除节点} else {pre = cur;//向后遍历}cur = cur.next;//向后遍历}return dummy.next;//返回头节点}
}

时间复杂度:O(n);(一个while循环遍历链表为n)

空间复杂度:O(1);(使用多一个伪头节点)

Leetcode 707.设计链表  

题目链接:707.设计链表

大佬视频讲解:设计链表讲解视频

个人思路

直接上代码,手撕链表必须理解记忆的东西。

解法

理解记忆代码;单双链表

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

Leetcode   206.反转链表 

题目链接:206.反转链表

大佬视频讲解:反转链表讲解视频

个人思路

使用双指针发,用一个临时变量指针做跳板,更换节点的next指向

解法
双指针

一共用三个节点,cur,pre,temp。首先要把 cur->next 节点用tmp指针保存一下,接下来要改变 cur->next 的指向了,将cur->next 指向pre ,此时已经反转了第一个节点了。然后循环走如下代码逻辑了,继续移动pre和cur指针。到最后,cur 指针已经指向了null,循环结束,链表也反转完毕,返回新的头节点pre即可。

这种利用temp暂存指针的 替换两个节点的方法会在链表经常用到,写出这个替换方法代码就相当于接火车一样,写出第一个temp=cur.next,那下一个就是cur.next开头去写,后续一样。

class Solution {public ListNode reverseList(ListNode head) {ListNode pre = null;ListNode cur = head;ListNode temp = null;while (cur != null) {temp = cur.next;// 保存下一个节点cur.next = pre;pre = cur;cur = temp;}return pre;}
}

时间复杂度:O(n);(模拟遍历二维矩阵的时间)

空间复杂度:O(1);(使用一个temp节点)

递归法

递归和上面的双指针差不多,就是需要多一个

class Solution {public ListNode reverseList(ListNode head) {return reverse(null, head);}private ListNode reverse(ListNode prev, ListNode cur) {if (cur == null) {return prev;}ListNode temp = null;temp = cur.next;// 先保存下一个节点cur.next = prev;// 反转// 更新prev、cur位置// prev = cur;// cur = temp;return reverse(cur, temp);}
}

时间复杂度:O(n);(要递归处理链表的每个节点)

空间复杂度:O(n);(递归调用了 n 层栈空间)

以上是个人的思考反思与总结,若只想根据系列题刷,参考卡哥的网址代码随想录算法官网

这篇关于算法打卡day3|链表篇|Leetcode 203.移除链表元素、 707.设计链表 、 206.反转链表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

csu1329(双向链表)

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

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费

怎么让1台电脑共享给7人同时流畅设计

在当今的创意设计与数字内容生产领域,图形工作站以其强大的计算能力、专业的图形处理能力和稳定的系统性能,成为了众多设计师、动画师、视频编辑师等创意工作者的必备工具。 设计团队面临资源有限,比如只有一台高性能电脑时,如何高效地让七人同时流畅地进行设计工作,便成为了一个亟待解决的问题。 一、硬件升级与配置 1.高性能处理器(CPU):选择多核、高线程的处理器,例如Intel的至强系列或AMD的Ry