首页 > 其他分享 >Day03 链表part01| LeetCode 203. 移除链表元素,707. 设计链表,206. 反转链表

Day03 链表part01| LeetCode 203. 移除链表元素,707. 设计链表,206. 反转链表

时间:2024-09-08 18:29:11浏览次数:8  
标签:203 ListNode cur val next 链表 移除 public

链表理论基础

  • 链表
    • 一种通过指针串联在一起的线性结构
      • 数据域
      • 指针域(存放指向下一个节点的指针,最后一个节点的指针域指向NULL)
    • 入口节点——head头节点
  • 链表类型
    • 单链表
    • 双链表
      • 两个指针域
        • 一个指向下一个节点
        • 一个指向上一个节点
    • 循环链表
      • 首尾相连
      • 约瑟夫环问题
  • 链表存储方式
    • 数组:在内存中连续分布
    • 链表:通过指针域的指针链接在内存中的各个节点,散乱分布在内存中的某地址上,分配机制取决于操作系统的内存管理

移除链表元素

203. 移除链表元素

public class HelloWorld {

    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;
        }
    }
    class Solution {
        public ListNode removeElements(ListNode head, int val)
        {
        if(head==null)
        {
            return 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;


        }
    }
    public static void main(String[] args) {


    }
}

设计链表

707. 设计链表

 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;
        }
    }
    class MyLinkedList {
        //链表元素个数
        int size;
        //虚拟头节点
        ListNode head;

        //初始化链表
        public MyLinkedList() {
            size=0;
            head=new ListNode(0);
        }

        public int get(int index) {
            if(index<0||index>=size)
            {
                return -1;
            }
            ListNode cur=head;
            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) {
            // 在最后一个节点 后 增加一个节点 == 在第size+1 个元素添加
            addAtIndex(size,val);

        }

        public void addAtIndex(int index, int val) {
                // 在下标为Index的位置前面,增加一个节点
            if(index>size)
            {
                return;
            }
            if(index<0)
            {
                index=0;
            }
            size++;
            ListNode pre=head;
            for(int i=0;i<index;i++)
            {
                pre=pre.next;
            }
            ListNode node=new ListNode(val);
            node.next=pre.next;
            pre.next=node;

        }

        public void deleteAtIndex(int index) {
            //  删除下标为Index的节点
            if(index<0||index>size)
            {
                return;
            }
            size--;
            if(index==0)
            {
                head=head.next;

            }
            else
            {
                ListNode pre=head;
                for(int i=0;i<index;i++)
                {
                    pre=pre.next;
                }
                pre.next=pre.next.next;
            }


        }
    }

反转链表

206. 反转链表

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre=null;
        ListNode cur=head;
        ListNode temp;

        while(cur!=null)
        {
            temp=cur.next;
            cur.next=pre;

            //更新pre和cur指针
            pre=cur;
            cur=temp;//  cur=cur.next;



        }
        return pre;
    }
}

标签:203,ListNode,cur,val,next,链表,移除,public
From: https://www.cnblogs.com/FreeDrama/p/18403204

相关文章

  • Day04 链表part02| LeetCode 24. 两两交换链表中的节点,19. 删除链表的倒数第 N 个,160.
    两两交换链表中的节点24.两两交换链表中的节点classSolution{publicListNodeswapPairs(ListNodehead){//设置虚拟头节点ListNodedummy=newListNode(0,head);ListNodecur=dummy;while(cur.next!=null&......
  • 20240911_220441 公共基础 线性链表
    什么是线性链表单向线性链表双向线性链表带链的栈带链队列线性链表的运算循环链表考点小结习题c习题a习题b习题c......
  • 陈润生院士新书推荐:中国生物信息学2035发展战略
    生物信息学(bioinformatics)是生命科学与计算机科学、信息科学、数学、统计学、系统科学等多学科相互交融而成的新兴学科。随着生命科学领域研究范式的变革,生物信息学已经从一门新兴交叉学科,发展成为催生生命科学领域新的研究方向和重大科学发现的重要原动力,也成为各国在生命健康和......
  • 数据结构基础讲解(三)——线性表之循环链表专项练习
    本文数据结构讲解参考书目:通过网盘分享的文件:数据结构 C语言版.pdf链接: https://pan.baidu.com/s/159y_QTbXqpMhNCNP_Fls9g?pwd=ze8e 提取码:ze8e数据结构基础讲解(二)——线性表之单链表专项练习-CSDN博客 个人主页:樱娆π-CSDN博客目录循环链表双向链表......
  • 003——单链表
    1.链式存储的特点逻辑(通过指针实现)上相邻,物理上可相邻可不相邻2.结点(节点都可以)4(&8)8(&6)6(&1)1(&9)9(NULL)4后面存上8的地址8后面存上6的地址6后面存上1的地址1后面存上9的地址9后面存上空地址也就是说,在链表中,需要存储:数据本身+下一个数据的地址,大体结构如下:数......
  • 【数据结构】单链表专题
    链表的概念及结构概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表的结构跟火车车厢相似,淡季时车次的车厢会相应减少,旺季时车次的车厢会额外增加几节。只需要将火车里的某节车厢去掉/加上,不会影响其他车......
  • 数据结构基础讲解(二)——线性表之单链表专项练习
    本文数据结构讲解参考书目:通过网盘分享的文件:数据结构 C语言版.pdf链接: https://pan.baidu.com/s/159y_QTbXqpMhNCNP_Fls9g?pwd=ze8e 提取码:ze8e 上一节我讲了线性表中顺序表的定义以及常用的算法,那么这节我将继续讲解顺序表中的链式结构以及常见的算法。数据......
  • 单双链表
    AcWing826.单链表模板题:实现一个单链表,链表初始为空,支持三种操作:向链表头插入一个数;删除第k个插入的数后面的一个数;在第k个插入的数后插入一个数。现在要对该链表进行M次操作,进行完所有操作后,从头到尾输出整个链表。注意:题目中第k个插入的数并不是指当前链表......
  • 信息学奥赛初赛天天练-85-NOIP2014普及组-基础题4-链表、随机存取、顺序存取、二分查
    信息学奥赛初赛天天练-85-NOIP2014普及组-基础题4-链表、随机存取、顺序存取、二分查找、二分比较、循环结构、图领奖PDF文档公众号回复关键字:202409071NOIP2014普及组基础题49下列选项中不属于图像格式的是()AJPEG格式BTXT格式CGIF格式DPNG格式1......
  • Java-单向链表实现
    什么是链表?        链表是一种常见的数据结构,用于存储一系列元素。与数组不同,链表中的元素(节点)在内存中不必是连续的。每个节点包含数据部分和指向下一个节点的引用(指针)。链表的主要优点是插入和删除操作的时间复杂度为O(1),但访问特定元素的时间复杂度为O(n)。头节点......