203.移除链表元素|707.设计链表|206.反转链表

这篇具有很好参考价值的文章主要介绍了203.移除链表元素|707.设计链表|206.反转链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

链表

203. 移除链表元素

/**
 * 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* dummyNode = new ListNode(0);
        dummyNode->next = head;


        //当前节点
        ListNode* cur = dummyNode;
        //遍历链表
        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 = dummyNode->next;
        delete dummyNode;
        return head;
    }
};

这里以链表 1 4 2 4 来举例,移除元素4。

203.移除链表元素|707.设计链表|206.反转链表

如果使用C,C++编程语言的话,不要忘了还要从内存中删除这两个移除的节点, 清理节点内存之后如图:

203.移除链表元素|707.设计链表|206.反转链表

其实可以设置一个虚拟头结点,这样原链表的所有节点就都可以按照统一的方式进行移除了。

来看看如何设置一个虚拟头。依然还是在这个链表中,移除元素1。

203.移除链表元素|707.设计链表|206.反转链表

这里来给链表添加一个虚拟头结点为新的头结点,此时要移除这个旧头结点元素1。

这样是不是就可以使用和移除链表其他节点的方式统一了呢?

来看一下,如何移除元素1 呢,还是熟悉的方式,然后从内存中删除元素1。

最后呢在题目中,return 头结点的时候,别忘了 return dummyNode->next;, 这才是新的头结点

707. 设计链表

这道题目设计链表的五个接口:

  • 获取链表第index个节点的数值
  • 在链表的最前面插入一个节点
  • 在链表的最后面插入一个节点
  • 在链表第index个节点前面插入一个节点
  • 删除链表的第index个节点

可以说这五个接口,已经覆盖了链表的常见操作,是练习链表操作非常好的一道题目

采用的设置一个虚拟头结点(这样更方便一些,大家看代码就会感受出来)【避免了要将头结点单独抽逻辑出来操作的麻烦】文章来源地址https://www.toymoban.com/news/detail-505489.html

class MyLinkedList {
public:
struct LinkedNode{
    int val;
    LinkedNode* next;
    LinkedNode(int val):val(val),next(nullptr){}
};

//声明一个私有成员变量
private:
    LinkedNode* _dummyHead;
    int _size;    

public:
    MyLinkedList() {
         _dummyHead = new LinkedNode(0);
         _size = 0;
    }
    
    int get(int index) {
        //判断index合法性
        if(index > (_size - 1) || index < 0){
            return -1;
        }
        //因为索引值是从原链表算,需要将头节点放在虚拟节点后一位
        LinkedNode* cur = _dummyHead->next;
        //index是从0开始的,0就是头结点
        while(index--){
            cur = cur->next;
        }
        return cur->val;
    }
    
    void addAtHead(int val) {
        //构造新节点
        LinkedNode* newNode = new LinkedNode(val);
        //添加操作 先将添加的节点指向插入的位置
        //再将原来的头结点指向新节点完成添加
        //如果先将dummyHead指向新节点,会丢失新节点指向的下一节点的位置
        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++;
    }
    
    void addAtIndex(int index, int val) {

        if(index > _size) return;
        //index<0 就在头部插入节点
        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++;

    }
    
    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,而是随机值
        //所以需要将tmp置空
        tmp = nullptr;
        _size--;

    }
};

/**
 * 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);
 */
206. 反转链表
/**
 * 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) {
        ListNode* pre = nullptr;
        ListNode* cur = head;

        //利用两个指针改变指针指向
        //tmp:当改变指向时有可能会丢失后面的指向,提前保存

        while(cur != nullptr){
            ListNode* tmp = cur->next;
            cur->next = pre;
            //改变指向后移动指针
            pre = cur;
            cur = tmp;
             
        }
        return pre;
    }
};

到了这里,关于203.移除链表元素|707.设计链表|206.反转链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法训练第三天|203.移除链表元素、707.设计链表、206.反转链表

    题目链接:力扣 思路:删除链表元素与数组不同之处在于,它需要被删除链表元素的前一个元素和后一个元素的参与,而不需要其他元素的参与。 我们使被删除元素前一个元素的指针指向被删除元素的后一个元素 ,也就是直接跳过被删除的元素,来实现删除。 同时我们考

    2024年02月05日
    浏览(39)
  • day3_203移除链表元素_707设计链表_206反转链表

    链表是一种通过指针串联起的线性结构,每个节点由两部分组成: 一个数据域,一个指针域(存放指向下一节点的指针),最后一个节点的指针域指向null。 链表入口节点是头结点head。 双链表:两个指针域,指向下一节点和上一节点。( 向前向后查询) 循环链表:首尾相连

    2024年02月16日
    浏览(33)
  • day3-链表理论基础 203.移除链表元素 707.设计链表 206.反转链表

    单链表 双链表:每个节点有两个指针域,一个指向下一个节点,一个指向上一个节点 既可以查询前一个节点,又能查询后一个节点 循环列表:链表首尾相连 在内存上 不是连续分布 的,散乱分布在内存中的某地址上 删除节点:next指针直接指向下下个节点,且在内存中删除

    2024年02月04日
    浏览(34)
  • 代码随想录day3 | 203.移除链表元素 707.设计链表 206.反转链表

    直接让前一个节点指向后一个节点即可 两种方法 第一种:直接删除 第二种:头删的时候,直接 head=head-next 其实这两种方法都没有做到统一 第三种:虚拟头结点法 这样的话,咱们删除的时候,就是以统一的规则来进行删除啦! 203.移除链表元素 法一:原始删除法 1、while(h

    2024年02月16日
    浏览(39)
  • 【代码随想录刷题记录】 203.移除链表元素 、 707.设计链表 、206.反转链表

    题目 给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。 题目链接:https://leetcode.cn/problems/remove-linked-list-elements/ 代码 小结 该题主要注意链表删除的操作以及在特殊情况下如何进行操作。特殊情况包括头结点为目标

    2024年02月08日
    浏览(47)
  • 【Leetcode60天带刷】day03链表——203. 移除链表元素,707.设计链表,206. 反转链表

    链表就像一串小火车,有一节一节的车厢,每个车厢都叫做一个节点。  单链表:每个链表车厢里有两个内容,一个放的是真正的数据,另一个放的是下一节车厢的编号。 双链表:每个链表车厢里有三个内容,一个真正数据,一个下一个车厢的编号,还有一个上一节车厢的编

    2024年02月06日
    浏览(48)
  • 【LeetCode题目详解】 203. 移除链表元素707. 设计链表206. 反转链表 day3(补)

    题意:删除链表中等于给定值 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], val = 7 输出:[] 看到这道题就想到了链表 这道题有两种写法,涉及如下链表操作的两种方式: 直接使用

    2024年02月16日
    浏览(42)
  • 复习Day05:链表part01:203.移除链表元素、707.设计链表、206.反转链表、234. 回文链表

    之前的blog链接:https://blog.csdn.net/weixin_43303286/article/details/131700482?spm=1001.2014.3001.5501 我用的方法是在leetcode再过一遍例题,明显会的就复制粘贴,之前没写出来就重写,然后从拓展题目中找题目来写。辅以Labuladong的文章看。然后刷题不用CLion了,使用leetcode自带模拟面试环境。

    2024年02月07日
    浏览(38)
  • 代码随想录Day3|链表理论基础|203.移除链表元素|707.设计链表|206.反转链表

    虽然以前写过一次链表,但是真的已经忘得一干二净了 链表 :通过 指针 串联在一起的线性结构,每个 节点 都由数据域和指针域组成。 指针域 :存放下一个节点的指针,最后一个节点的指针域指向null,也即空指针 head :链表的入口节点,也即链表的头节点 链表的类型 单

    2024年02月11日
    浏览(54)
  • 刷题日记 Day 3 : Leetcode 203 . 移除链表元素、Leetcode 707 . 设计链表、Lettcode 206 . 反转链表

    本篇文章 , 是在代码随想录 60 天编程挑战的基础上进行的题目讲解 参与链接在此 : https://programmercarl.com/other/xunlianying.html 大家好 , 这个专栏 , 给大家带来的是 60 天刷题强训 . 最令大家头疼的事就是刷题了 , 题目又臭又长又抽象 , 有的题读都读不懂 , 更别说做了 . 所以 , 这个

    2023年04月09日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包