首页 > 其他分享 >leetcode刷题day3|链表部分( 203.移除链表元素、707.设计链表、206.反转链表)

leetcode刷题day3|链表部分( 203.移除链表元素、707.设计链表、206.反转链表)

时间:2024-08-31 16:50:08浏览次数:15  
标签:203 ListNode cur val head next 链表 移除

前言:链表部分之前刷过一些题,掌握的还可以,希望可以顺利把这部分题刷完。

203.移除链表元素

思路:自己创建一个头节点,使新的头节点指向旧的头节点。
错误尝试:一开始考虑的比较复杂,设置了指针pre,能够想到直接比较cur.next.val和val的值会使代码更加简洁,但也要注意想清楚如果删除元素后cur是否需要向前走一步,答案是不需要的。因为删除之后cur.next已经发生了变化。
代码如下:

/**
 - 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) {
        ListNode newHead=new ListNode();
        newHead.next=head;
        ListNode cur=newHead;
        while(cur.next!=null){
            if(cur.next.val==val){
                cur.next=cur.next.next;
            }else{
                cur=cur.next;
            }
        }
        return newHead.next;
    }
}

707. 设计链表

前言:确实很少训练到链表设计的基础,这个题让我掌握如何从节点开始建立链表,并实现各种接口。
思路:该题存在一个接口需要在头节点前面插入节点,所以最好设置一个虚拟头节点。
1、需要先设计一个节点类。有以下好处:

  • 封装性: 将节点定义为一个独立的类可以更好地隐藏内部实现细节。这样外部代码不需要知道节点的具体结构,只需要通过链表类提供的方法来操作链表。
  • 重用性: Node 类可以在多个不同的数据结构中被复用,比如不仅可以用于单向链表,还可以用于双向链表、循环链表等。这种设计使得 Node类更加通用。
  • 清晰性: 将节点逻辑和链表逻辑分离可以使代码更加清晰易懂。每个类都有明确的责任,这有助于维护和扩展。
    节点类的实现代码如下:
class ListNode{
   int val;
   ListNode next;
   ListNode(){};
   ListNode(int val){
       this.val=val;
   }
}

2、单链表

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) {
        ListNode headNode=new ListNode(val);
        headNode.next=head.next;
        head.next=headNode;
        size++;
    }
    
    public void addAtTail(int val) {
        ListNode cur=head;
        while(cur.next!=null){
            cur=cur.next;
        }
        ListNode tailNode=new ListNode(val);
        tailNode.next=cur.next;
        cur.next=tailNode;
        size++;
    }
    
    public void addAtIndex(int index, int val) {
        if(index>size){
            return;
        }
        if(index<0){
            index=0;
        }
        ListNode cur=head;
        for(int i=0;i<index;i++){
            cur=cur.next;
        }
        ListNode indexNode=new ListNode(val);
        indexNode.next=cur.next;
        cur.next=indexNode;
        size++;
    }
    
    public void deleteAtIndex(int index) {
        if(index<0 || index>=size){
            return;
        }
        ListNode pre=head;
        for(int i=0;i<index;i++){
            pre=pre.next;
        }
        pre.next=pre.next.next;
        size--;
    }
}

总结:写的时候一定注意虚拟头节点的存在以及size的变化。还是挺不好写的,有很多细节,之后要多练习。注意size和index的关系,index>=size都是无效的,总是会忘记相等的情况。

206.反转链表

前言:反转链表之前写过,印象很深刻是头插+递归。但自己写的时候递归的条件和函数想不起来了。感觉之前其实是死记硬背的反转链表的递归写法,对原理掌握的并不清楚。这次通过先写双指针的写法,再写递归,整个逻辑更清晰了。

  • 双指针写法的代码
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre=null;
        ListNode cur=head;
        while(cur!=null){
            ListNode temp=cur.next;
            cur.next=pre;
            pre=cur;
            cur=temp;
        }
        return pre;
    }
}

代码优化一下,把temp的定义写在循环外面就不用买次重新定义了:

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;
    }
}
  • 递归写法的代码
class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(null,head);
    }
    public ListNode reverse(ListNode pre,ListNode cur){
        if(cur==null){
            return pre;
        }
        ListNode temp=cur.next;
        cur.next=pre;
        return reverse(cur,temp);
    }
}
  • 从后往前反转递归
    印象中之前是背的这种方法,但是没理解透。
    思路:
    1、边缘条件判断,也就是链表为空或者只有一个节点的情况,这种情况直接返回head。
    2、进行递归调用,返回值为后面的一个结点last。传入头节点的下一个节点,因为运行到递归这一行的时候没有达到边缘条件所以会多次调用递归,直到最后一个节点,因为最后一个节点的next为null,此时在这一层递归中last就是最后一个节点。
    3、回到上一层递归继续执行,此时的head为倒数第二个节点,进行反转给head节点的next节点(也就是最后一个节点)的next赋值为head,完成head和head.next的反转。并将head的next域赋值为null,这一层的反转结束,回到上一层继续完成反转。
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;
    }
}

总结:反向反转链表理解起来还是比较困难的。但是双指针和正向反转链表还可以,可以先掌握这两种方法。

标签:203,ListNode,cur,val,head,next,链表,移除
From: https://blog.csdn.net/m0_51007517/article/details/141718314

相关文章

  • 数据结构-单链表-详解-2
    数据结构-单链表-详解-21.前言2.创建新结点3.头插与尾插3.1头插3.2尾插空链表找尾4.头删与尾删4.1头删4.2尾删1.前言在数据结构-单链表-详解-1中,我们不仅了解了单链表的基本概念,还掌握了如何创建和打印单链表。今天,我将详细讲解如何对单链表进行头尾部的插入、......
  • 单链表应用
    基于单链表实现通讯录项目//Contact.c#define_CRT_SECURE_NO_WARNINGS1#include"contact.h"#include"list.h"//初始化通讯录voidInitContact(contact**con){ con=NULL; }//添加通讯录数据voidAddContact(contact**con){ PeoInfoinfo; printf("addres......
  • 单链表
    目录1.链表的概念及结构2.单链表的实现3.链表的分类                        1.链表的概念及结构概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 链......
  • 代码随想录算法day4 - 链表2
    题目124.两两交换链表中的节点给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。示例1:输入:head=[1,2,3,4]输出:[2,1,4,3]示例2:输入:head=[]输出:[]示例3:输入:head=[1]输出:[1]......
  • list容器---深入探索STL中的双向链表
    目录一、引言二、list容器原理三、list容器的常用操作  1.创建list容器  2.添加元素  3.删除元素  4.访问元素  5.遍历list容器四、list容器的优缺点五、实际应用场景六、总结        本文将详细介绍C++STL中的list容器,包括其原理、常用......
  • 代码随想录算法训练营,8月30日 | 203.移除链表元素, 707.设计链表, 206.反转链表
    链表理论基础1.单链表:数据域和指针域(指向下一个结点的位置)组成,头结点,结尾为空指针;双链表:多了一个指向前一个结点的指针;循环链表:结尾指向头结点。2.链表在内存中的存储不是顺序的,跟数组不同,要找一个数据只能通过前一个数据来找,所有这就导致链表的查询比数组麻烦,但是插入删除数据......
  • 顺序表和链表知识点
    1顺序表顺序表是指用一段物理地址连续的空间去存储数据的线性结构。顺序表有两种:静态顺序表,动态顺序表。1.1静态顺序表结构体定义typedefintElemDataSL;typedefstructSequeList{ ElemDataSLarr[100]; intsize;}SL;静态顺序表在创建结构体的时候就已经把......
  • 分享丨【题单】链表、二叉树与一般树(前后指针/快慢指针/DFS/BFS/直径/LCA)
    作者:灵茶山艾府链接:https://leetcode.cn/circle/discuss/K0n2gO/一、链表注:由于周赛中的链表题可以转成数组处理,难度比直接处理链表低,故不标明难度分。带着问题去做下面的题目:在什么情况下,要用到哨兵节点(dummynode)?在什么情况下,循环条件要写while(node!=null)?什么情况......
  • 代码随想录算法day3 - 链表1
    题目1203.移除链表元素给你一个链表的头节点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],v......
  • 数据结构-单链表-详解-1
    数据结构-单链表-详解-11.前言2.结点3.打印3.1关于断言3.2下一结点的找法物理结构逻辑结构1.前言在数据结构-顺序表-详解中,我详细介绍了顺序表的实现,而顺序表也有一些缺点:中间,头部插入时,需整体挪动数据,效率低下。空间不够时扩容,有一定的消耗,也可能有一定空间浪费......