首页 > 其他分享 >代码随想录day3 | LeetCode203. 移除链表元素、LeetCode707. 设计链表、LeetCode206. 反转链表

代码随想录day3 | LeetCode203. 移除链表元素、LeetCode707. 设计链表、LeetCode206. 反转链表

时间：2024-08-17 16:26:01浏览次数：13  
标签：index head ListNode cur val 随想录 next 链表 移除

代码随想录day3 | LeetCode203. 移除链表元素、LeetCode707. 设计链表、LeetCode206. 反转链表

为了防止早上写博客上传图片失败，今天试试下午写，发现图片上传正常

链表基础

文章链接：链表基础

C/C++的定义链表节点方式，如下所示：

// 单链表
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数(初始化列表方式)
};

不定义构造函数时，C++默认生成一个构造函数。

但是这个构造函数不会初始化任何成员变量，下面我来举两个例子：

通过自己定义构造函数初始化节点：

ListNode* head = new ListNode(5);

使用默认构造函数初始化节点：

ListNode* head = new ListNode();
head->val = 5;

所以如果不定义构造函数使用默认构造函数的话，在初始化的时候就不能直接给变量赋值！

移除链表元素

题目链接：LeetCode203. 移除链表元素

自己敲

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* H = new ListNode(0,head);//虚拟头结点
        H->next = head;
        ListNode* p = H;
        while (p->next != nullptr) {//要判断是否删除的元素是p->next，所以当p->next为null时，链表已经遍历完
            if(p->next->val == val) {
                p->next = p->next->next;
            }
            p = p->next;
        }
        return H->next;
    }
};

运行时报错

Line 17: Char 19: runtime error: member access within null pointer of type 'ListNode' (solution.cpp)

大致意思是：试图访问ListNode空指针类型的成员

为什么会出现这种错误？

自己检查代码逻辑发现，

if(p->next->val == val) {
    p->next = p->next->next;
}
p = p->next;

一层while循环中，如果删除了某个元素，此时p->next指向了下一个要判断是否删除的元素，然后p = p->next，跳过了这个未判断是否删除的元素，如果跳过之后元素为空，下一轮while判断时，会访问null->next，报错

如图，删除元素后，此时p->next已经指向了下一个待判断是否需要被删除的元素
在这里插入图片描述

如果当前元素无需删除，则执行p=p->next，将p和p->next后移

修改代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* H = new ListNode(0,head);//虚拟头结点
        ListNode* p = H;
        while (p->next != nullptr) {//要判断是否删除的元素是p->next，所以当p->next为null时，链表已经遍历完
            if(p->next->val == val) {
                p->next = p->next->next;
            }else{
                p = p->next;
            }
        }
        return H->next;
    }
};

看题解

链接
C/C++别忘了自己手动删除内存

设置一个虚拟头结点在进行移除节点操作：

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
        dummyHead->next = head; // 将虚拟头结点指向head，这样方便后面做删除操作
        ListNode* cur = dummyHead;
        while (cur->next != NULL) {
            if(cur->next->val == val) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            } else {
                cur = cur->next;
            }
        }
        head = dummyHead->next;
        delete dummyHead;
        return head;
    }
};

直接使用原来的链表来进行移除节点操作：

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // 删除头结点
        while (head != NULL && head->val == val) { // 注意这里不是if
            ListNode* tmp = head;
            head = head->next;
            delete tmp;
        }

        // 删除非头结点
        ListNode* cur = head;
        while (cur != NULL && cur->next!= NULL) {
            if (cur->next->val == val) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            } else {
                cur = cur->next;
            }
        }
        return head;
    }
};

细节：

  • NULL和nullptr

    • 用NULL代替空指针在C++程序中会出现二义性，为解决NULL代指空指针存在的二义性问题，在C++11版本(2011年发布)中特意引入了nullptr这一新的关键字来代指空指针

    • NULL在C++中就是0，这是因为在C++中void* 类型是不允许隐式转换成其他类型的，所以之前C++中用0来代表空指针，但是在重载整形的情况下，会出现上述的问题。所以，C++11加入了nullptr，可以保证在任何情况下都代表空指针，而不会出现上述的情况，因此，建议以后还是都用nullptr替代NULL吧，而NULL就当做0使用。

    • 详细内容参考：C++中NULL和nullptr的区别

总结

  • 虚拟头结点的使用

  • C/C++别忘了自己手动删除内存（包括自己定义的头结点）

  • p->next指向待判断是否删除的元素，p指向其前一个元素，这样便于删除链表元素

  • p->next = p->next->next已经将p->next（指向判断是否删除的元素）向后移动，无需再p = p->next

  • c++中尽量用nullptr

设计链表

题目链接：LeetCode707. 设计链表

自己敲

class MyLinkedList {
public:
    struct LinkNode{
        int val;
        LinkNode* next;
        LinkNode(int x):val(x),next(nullptr){}
        LinkNode():next(nullptr){}
    };
    
    MyLinkedList() {
        LinkNode* dummyHead = new LinkNode(0);
        LinkNode* head = new LinkNode();
        dummyHead->next =head;
    }
    
    int get(int index) {
        LinkNode* p = dummyHead;
        while(index--){
            p=p->next;
        }
        return p->next = nullptr ? -1 :p->next->val;
    }
    
    void addAtHead(int val) {
        LinkNode* t = new LinkNode(val);
        t->next = dummyHead->next;
        dummyHead->next = t;
    }
    
    void addAtTail(int val) {
        LinkNode* p = dummyHead;
        while(p->next!=nullptr){//找到末尾结点
            p = p->next;
        }
        LinkNode* t = new LinkNode(val);
        p->next = t;
        t->next = nullptr;
    }
    
    void addAtIndex(int index, int val) {
        LinkNode *p = dummyHead;
        while(index--){
            p = p->next;
        }
        LinkNode* t = new LinkNode(val);
        t->next = p->next;
        p->next = t;
    }
    
    void deleteAtIndex(int index) {
        LinkNode* p = dummyHead;//为了删除元素而创建的指针p，让p->next指向待判断是否删除元素，便于删除
        while(index--){
            p=p->next;
        }
        return p->next = nullptr ? -1 :p->next->val;
        LinkNode* tmp = p->next;
        p->next=p->next->next;
        delete tmp;
    }
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

然后报错
在这里插入图片描述
时间不够了，直接看题解吧

看题解

链接

采用虚头结点

class MyLinkedList {
public:
    // 定义链表节点结构体
    struct LinkedNode {
        int val;
        LinkedNode* next;
        LinkedNode(int val):val(val), next(nullptr){}
    };

    // 初始化链表
    MyLinkedList() {
        _dummyHead = new LinkedNode(0); // 这里定义的头结点 是一个虚拟头结点，而不是真正的链表头结点
        _size = 0;
    }

    // 获取到第index个节点数值，如果index是非法数值直接返回-1， 注意index是从0开始的，第0个节点就是头结点
    int get(int index) {
        if (index > (_size - 1) || index < 0) {
            return -1;
        }
        LinkedNode* cur = _dummyHead->next;
        while(index--){ // 如果--index 就会陷入死循环
            cur = cur->next;
        }
        return cur->val;
    }

    // 在链表最前面插入一个节点，插入完成后，新插入的节点为链表的新的头结点
    void addAtHead(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        newNode->next = _dummyHead->next;
        _dummyHead->next = newNode;
        _size++;
    }

    // 在链表最后面添加一个节点
    void addAtTail(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = _dummyHead;
        while(cur->next != nullptr){
            cur = cur->next;
        }
        cur->next = newNode;
        _size++;
    }

    // 在第index个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
    // 如果index 等于链表的长度，则说明是新插入的节点为链表的尾结点
    // 如果index大于链表的长度，则返回空
    // 如果index小于0，则在头部插入节点
    void addAtIndex(int index, int val) {

        if(index > _size) return;
        if(index < 0) index = 0;        
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = _dummyHead;
        while(index--) {
            cur = cur->next;
        }
        newNode->next = cur->next;
        cur->next = newNode;
        _size++;
    }

    // 删除第index个节点，如果index 大于等于链表的长度，直接return，注意index是从0开始的
    void deleteAtIndex(int index) {
        if (index >= _size || index < 0) {
            return;
        }
        LinkedNode* cur = _dummyHead;
        while(index--) {
            cur = cur ->next;
        }
        LinkedNode* tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        //delete命令指示释放了tmp指针原本所指的那部分内存，
        //被delete后的指针tmp的值（地址）并非就是NULL，而是随机值。也就是被delete后，
        //如果不再加上一句tmp=nullptr,tmp会成为乱指的野指针
        //如果之后的程序不小心使用了tmp，会指向难以预想的内存空间
        tmp=nullptr;
        _size--;
    }

    // 打印链表
    void printLinkedList() {
        LinkedNode* cur = _dummyHead;
        while (cur->next != nullptr) {
            cout << cur->next->val << " ";
            cur = cur->next;
        }
        cout << endl;
    }
private:
    int _size;
    LinkedNode* _dummyHead;

};

总结

我代码存在的问题：

  • 类里面没有成员变量 _size _dummyHead，在添加元素后_size++

  • 涉及index处没有判断下标合法性

  • delete tmp;//被delete后的指针tmp的值（地址）并非就是NULL，而是随机值，此时tmp为野指针，如果之后的程序不小心使用了tmp，会指向难以预想的内存空间
tmp=nullptr;

反转链表

题目链接：LeetCode206. 反转链表

自己敲

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head = nullptr)    return nullptr;
        ListNode* p = nullptr;
        ListNode* q = head->next;
        while(q!=nullptr){
            head->next = p;
            p = head;
            head = q;
            q = q->next;
        }
        head->next = p;
        return head;
    }
};

报错
在这里插入图片描述

我明明判断了，如果head为null，直接返回，不明白为什么出现这种情况

看题解

链接

首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。

然后就要开始反转了，首先要把cur->next节点用tmp指针保存一下，也就是保存一下这个节点。

为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。

接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。

最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。 此时我们return pre指针就可以了，pre指针就指向了新的头结点。

双指针法
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* temp; // 保存cur的下一个节点
        ListNode* cur = head;
        ListNode* pre = NULL;
        while(cur) {
            temp = cur->next;  // 保存一下 cur的下一个节点，因为接下来要改变cur->next
            cur->next = pre; // 翻转操作
            // 更新pre 和 cur指针
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};
  • 在while中判断cur是否存在，如果为null，就不会执行循环体中temp = cur->next操作，不会出现空指针访问（访问null->next）

我代码问题：

  • 整体逻辑没问题，但是if(head = nullptr)不是判断是赋值，=改为==，编程要细心，如果定位到问题所在，不要怀疑自己，先自己看看代码是否真的实现了自己的逻辑，有没有语法错误
递归法

递归法相对抽象一些，但是其实和双指针法是一样的逻辑，同样是当cur为空的时候循环结束，不断将cur指向pre的过程。

关键是初始化的地方：双指针法中初始化 cur = head，pre = NULL，在递归法中可以从如下代码看出初始化的逻辑也是一样的，只不过写法变了。

class Solution {
public:
    ListNode* reverse(ListNode* pre,ListNode* cur){
        if(cur == NULL) return pre;
        ListNode* temp = cur->next;
        cur->next = pre;
        // 可以和双指针法的代码进行对比，如下递归的写法，其实就是做了这两步
        // pre = cur;
        // cur = temp;
        return reverse(cur,temp);
    }
    ListNode* reverseList(ListNode* head) {
        // 和双指针法初始化是一样的逻辑
        // ListNode* cur = head;
        // ListNode* pre = NULL;
        return reverse(NULL, head);
    }

};

上面的递归写法和双指针法实质上都是从前往后翻转指针指向，其实还有另外一种与双指针法不同思路的递归写法：从后往前翻转指针指向

见题解原文

总结

  • 核心思路：因为接下来要改变 cur->next 的指向了（从指向前方改变为指向后方），所以用一个哨兵来存储当前cur->next结点，以便cur在没有指针向前指的情况下还能前移

标签：index,head,ListNode,cur,val,随想录,next,链表,移除
From： https://blog.csdn.net/qq_74865904/article/details/141261795

相关文章

  • 「代码随想录算法训练营」第四十天 | 动态规划 part13
    647.回文子串题目链接：https://leetcode.cn/problems/palindromic-substrings/文章讲解：https://programmercarl.com/0647.回文子串.html题目难度：中等视频讲解：https://www.bilibili.com/video/BV17G4y1y7z9/题目状态：看题解思路一：动态规划使用一个二维动规数组dp[i][j]来保......
  • 合并K个升序链表-力扣
    /***Definitionforsingly-linkedlist.*structListNode{*intval;*ListNode*next;*ListNode():val(0),next(nullptr){}*ListNode(intx):val(x),next(nullptr){}*ListNode(intx,ListNode*next):val(x),next(ne......
  • 代码随想录算法训练营day09|151.翻转字符串里的单词，卡码网：55.右旋转字符串，28.实现 str
    151.翻转字符串里的单词题目链接：https://leetcode.cn/problems/reverse-words-in-a-string/description/暴力removeExtraSpaces：voidremoveExtraSpaces(string&s){for(inti=s.size()-1;i>0;i--){if(s[i]==''&&s[i]=......
  • 代码随想录day32 || 509 斐波那契数列，70 爬楼梯，746 最小代价爬楼梯
    509斐波那契数列funcfib(nint)int{ //dp五部曲 //1dp数组含义以及下标含义:本题保存的是完整的斐波那契数列，i对应数列的第i个数字 //2递推公式:F(n)=F(n-1)+F(n-2) //3dp数组初始化:由递推公式推到，0，1两位需要手动赋值，否则，oor //4遍历顺序:求......
  • 链表多选题（1）链表
    描述在一个链表中，已知p是指向结点c的指针变量，q是指向结点d的指针变量，s是指向结点h的指针变量，若在p和q之间插入结点s，则执行（） 输入描述无输出描述如果选择A选项，输出按照下面方法输出:示例#include<iostream>usingnamespacestd;intmain(){cout<<"AB";......
  • 【408DS算法题】016基础-倒序输出单链表的结点值
    Index题目分析实现总结题目给定单链表的头结点，倒序输出单链表的结点值。分析实现要倒序输出链表结点值，首先可以想到的是先将链表的结点值存储到数组中，然后利用数组随机访问的特性进行倒序输出。如果考虑其它思路的话，还可以使用栈来代替数组——将链表元素依次......
  • 代码随想录算法训练营第十七天（一）| 654.最大二叉树 617.合并二叉树
    654.最大二叉树题目：给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:创建一个根节点，其值为 nums 中的最大值。递归地在最大值 左边 的 子数组前缀上 构建左子树。递归地在最大值 右边 的 子数组后缀上 构建右子树。......
  • 代码随想录算法训练营第十七天（二）| 700.二叉搜索树中的搜索 98.验证二叉搜索树
    700.二叉搜索树中的搜索题目：给定二叉搜索树（BST）的根节点 root 和一个整数值 val。你需要在BST中找到节点值等于 val 的节点。返回以该节点为根的子树。如果节点不存在，则返回 null 。示例1:输入：root=[4,2,7,1,3],val=2输出：[2,1,3]示例2:输入：roo......
  • 链表中环的检测与入口节点的查找：哈希表与快慢指针方法
    前言在数据结构中，链表是一种常见的线性数据结构。链表中的环问题是面试和实际编程中经常遇到的一个问题。本文将先复习哈希表的基本概念，然后介绍两种检测链表中环的方法：哈希表法和快慢指针法，并分析它们的优缺点、原理以及时间和空间复杂度。哈希表复习定义：哈希表，又称散列表，......
  • Python合并两个有序链表
    题目合并两个有序链表，如l1=[1,3,4],l2=[1,2,4,5]，合并后l3=[1,1,2,3,4,4,5]解决思路需要构建节点Node和链表LinkedList结构如果root节点不确定，可以创建一个哑节点Node(0)，作为root节点的前节点，也是初始节点(当前节点)循环当l1当前节点不为None并且l2当前节点不为None时，那个节......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99