代码编织梦想

1. 删除链表中所有值为val结点

OJ链接
在这里插入图片描述

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

这个题我们在上一篇博客中实现单向链表中展示过,这里不再赘述.

2. 反转一个单链表

OJ链接
在这里插入图片描述

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null){
            return head;//列表为空的情况
        }
        if(head.next == null){
            return head;//结点只有一个的情况
        }
        ListNode cur = head.next;
        ListNode curNext = cur.next;//防止下一个结点找不到,所以定义curNext
        head.next = null;//先把头结点的next置为null,否者返回时会越界
        while(cur != null){
            cur.next = head;
            head = cur;
            cur = curNext;//头插法
            if(curNext !=null){
                curNext = curNext.next;//防止走到最后的时候空指针异常
            }
        }
        return head;
    }
}

动态演示:

翻转链表

[注意]

  1. 需要定义一个nodeNext结点来找到下一个结点,**,cur想要往后走的时候,不是我们想要找的下一个结点,因为在链表头插法修改了next的地址,**为了防止下一个结点的地址丢失,所以我们引入curNext.
  2. 在一开始的时候,需要把head.next置为空,因为翻转链表之后,一开始的头结点将是新链表的最后一个结点,最后一个结点的next为null.
  3. 在循环体内部要判断curNext是否为null,若没有,cur走到了最后一个结点的时候,curNext就位null了,在执行curNext = curNext.next的时候,就会出现空指针异常.

3. 链表的中间结点

OJ链接
在这里插入图片描述

class Solution {
    public ListNode middleNode(ListNode head) {
        if(head == null){
            return head;
        }
        ListNode slow = head;
        ListNode fast = head;//定义双指针
        while (fast != null && fast.next != null){//顺序不可以反,否则会nullException,
        //第一个是奇数的终止情况,第二个是偶数
            fast = fast.next.next;//快指针走两步
            slow = slow.next;//慢指针走一步
        }
        return slow;//最后慢指针指向的就是中间结点
    }
}

动态演示

寻找中间结点


[注意]

  1. 这个题大多数人想到的是通过计数的方法来遍历链表,之后再/2,这种方法固然没错,但是它的时间复杂度较高,它遍历了两次链表,为了只遍历一次就通过,我们引入了快慢指针,快指针的速度是慢指针的2倍.
  2. 这个题分为奇数项和偶数项,针对不同的项数,限制条件也不同.while (fast != null && fast.next != null)
  3. 限制条件while (fast != null && fast.next != null)的两个条件不可以反,如果fast==null,后面的条件就会报空指针异常.

4. 返回倒数第k个节点

OJ链接
在这里插入图片描述

这道题我们加大一点难度,把说明的条件删去.

class Solution {
    public int kthToLast(ListNode head, int k) {
        if (head == null) {
            return head.val;
        }
        if(k < 0){//负数返回null
            return -1;
        }
        ListNode slow = head;
        ListNode fast = head;
        int count = 0;
        while (count != k - 1) {//先让fast走k-1步
            if (fast != null) {//防止k太大导致fast越界
                fast = fast.next;
                count++;
            } else {
                return -1;//如果越界返回null
            }
        }
        while (fast.next != null) {//fast指向最后一个结点就结束,所以加上next
            fast = fast.next;
            slow = slow.next;
        }
        return slow.val;
    }
}

动态演示

寻找倒数第k个结点


[注意]

  1. 这道题和上一道题一样,许多人首先想到的就是遍历链表,得到size,减去k之后再遍历,这种做法可通过,但是效率欠缺.所以我们又引入了快慢指针.
  2. 既然删掉了限制条件,那么k就有可能是无效的,其中一种就是k小于0,通过if(k < 0)来限制.越界的情况,很多人又想,这不是还得遍历数组去得到size吗?其实不用,只要限制快指针在第一次走的时候不越界即可.if (fast != null)
  3. fast指向最后一个节结点的时候,slow就是中间结点,所以避免在while (fast.next != null)把next去掉,否者slow就会多走一格.

5. 合并两个有序链表

OJ链接
在这里插入图片描述

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode node = new ListNode(-1);//引入傀儡结点
        ListNode heada = list1;
        ListNode headb = list2;
        ListNode tmp = node;//定义临时结点用于遍历
        while(heada != null && headb != null){//遍历两个链表
            if(heada.val < headb.val){//比较对应位置的大小
                tmp.next = heada;
                heada = heada.next;
                tmp = tmp.next;//连接对应结点
            }else{
                tmp.next = headb;
                headb = headb.next;
                tmp = tmp.next;
            }
        }
        if(headb == null){//判断最后谁先走完,没走完的链表后面的值一定比已经走完那个链表后面的值大,所以直接连上即可
            tmp.next = heada;
        }else{
            tmp.next = headb;
        }
        return node.next;
    }
}

动态演示

合并两个有序链表


[注意]

  1. 这里我们为了把为了把两个链表串起来,我们需要引入傀儡结点,就像想要用一根线串起零散的珠子需要给这根线的头按上一根针一样.
  2. 两个链表总会有其中一个会先走完,其实走完之后,未走完的链表后面的结点其实都已经比走完链表的尾结点大了,所以直接串上去即可.
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/2301_80050796/article/details/137159091

java - 数据结构之 顺序表与链表-爱代码爱编程

1. 线性表 ✍线性表是最基本、最简单、也是最常用的一种数据结构。线性表是数据结构的一种,一个线性表是n个具有相同特性的数据元素的有限序列。线性表就像是用一根绳子将我们的数据串起来存储到我们的内存中,并且线性表有且仅有一个开始结点和终端结点,开始结点没有前驱元素的且只有一个后驱元素,终端结点没有后驱元素且只有一个前驱元素,其他的结点有且只有一个前驱

java数据结构 & linkedlist & 链表-爱代码爱编程

文章目录 Java数据结构 & LinkedList & 链表链表背景知识1. LinkedList链表的模拟1. 1 MyLinkedList 基础摸版1.2 MyLinkedList基础属性1.3

数据结构:linkedlist类和链表_linkedlist没返回数据-爱代码爱编程

文章目录 1.前言2.LinkedList主要的操作3.模拟实现LinkedList3.1 模拟实现add方法3.2 模拟实现remove方法3.3 模拟实现clear方法 4.八道关于链表操作的题目4.

【详解linkedlist与链表】_创建链表linkedlist-爱代码爱编程

🌠作者:@TheMythWS. 🎇座右铭:不走心的努力都是在敷衍自己,让自己所做的选择,熠熠发光。 目录 链表 概念 图解链表 链表的实现  1.创建链表 2.遍历链表  3.查找是否包含关键字key是否在单链表当中  4.获取单链表的长度  5.头插法  6.尾插法  7.任意位置插入(假如第一个数据结点为0下

【数据结构和算法初阶(c语言)】二叉树的链式结构-爱代码爱编程

目录 ​编辑 1.二叉树的链式存储 2.二叉树链式结构的实现 2.1树的创建  2.2二叉树的再理解 3.链式结构二叉树的遍历 3.1前序遍历实现: ​编辑 3.2中序遍历实现 3.3后序遍历   ​编辑  4.链式二叉树节点数目的计算  4.1 总节点个数的计算 错误代码1: 错误

【数据结构】双向奔赴的爱恋 -爱代码爱编程

关注小庄 顿顿解馋๑ᵒᯅᵒ๑ 引言:上回我们讲解了单链表(单向不循环不带头链表),我们可以发现他是存在一定缺陷的,比如尾删的时候需要遍历一遍链表,这会大大降低我们的性能,再比如对于链表中的一个结点我们是无

数据结构02:线性表 链表习题02[c++]-爱代码爱编程

考研笔记整理~🥝🥝 之前的博文链接在此:数据结构02:线性表[顺序表+链表]_线性链表-CSDN博客~🥝🥝 本篇作为链表的代码补充,供小伙伴们参考~🥝🥝 第1版:王道书的课后习题~🧩🧩 编辑:梅头脑🌸 参考用书:王道考研《2025年 数据结构考研复习指导》 目录 🧵09年 查找单链表倒数第k个位置的节点 🧵12年 寻找单链表的相同后

go的数据结构与实现【stack】-爱代码爱编程

介绍 栈是存放值的一种特殊容器,在插入与删除值时,这种结构遵循后进先出(Last-in-first-out,LIFO)的原则,也就是说,值可以任意插入栈中,但每次取出的都是此前插入的最后一个值。 实现 栈必须支持以下方

探索数据结构:链式队与循环队列的模拟、实现与应用-爱代码爱编程

✨✨ 欢迎大家来到贝蒂大讲堂✨✨ 🎈🎈养成好习惯,先赞后看哦~🎈🎈 所属专栏:数据结构与算法 贝蒂的主页:Betty’s blog 1. 队列的定义 队列(queue)是一种只允许在一端进行插入操

实验三 高级数据结构(1) 并查集的应用+ treap树的应用-爱代码爱编程

目的: (1)熟悉并掌握并查集的应用 (2)熟悉并掌握BST (3)熟悉并掌握Treap树的建立与应用 实验内容: 1.严重急性呼吸系统综合症 (SARS) 是一种病因不明的非典型肺炎,于 2003 年 3 月中旬被公认为全球威胁。为了尽量减少传染给他人,最好的策略是将嫌疑人与其他人分开。 在不传播疾病大学 (NSYSU) 中,有许多学生团体

代码随想录阅读笔记-爱代码爱编程

题目 给定一个二叉树,检查它是否是镜像对称的。 思路  首先想清楚,判断对称二叉树要比较的是哪两个节点,要比较的可不是左右节点! 对于二叉树是否对称,要比较的是根节点的左子树与右子树是不是相互翻转的,理解这一点就知道了其实我们要比较的是两个树(这两个树是根节点的左右子树),所以在递归遍历的过程中,也是要同时遍历两棵树。 那么如何比较呢?

数据结构之快速排序-爱代码爱编程

目录 快速排序 1.分区操作 2.相遇位置小于枢轴元素 3.递归终止条件 4.代码优化:三数取中法 5.挖坑法实现快排 6.前后指针实现快排 快速排序 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其基本思想为:任取待排序元素序列中 的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所

深入理解数据结构第一弹——二叉树(1)——堆-爱代码爱编程

前言: 在前面我们已经学习了数据结构的基础操作:顺序表和链表及其相关内容,今天我们来学一点有些难度的知识——数据结构中的二叉树,今天我们先来学习二叉树中堆的知识,这部分内容还是非常有意思的,下面我们就开始慢慢学习 准备工作:本人习惯将文件放在test.c、SeqList.c、SeqList.h三个文件中来实现,其中test.c用来放主函数,S