算法-设计链表、移除链表元素、反转链表

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

伪装成一个老手!

设计链表

题目

设计一个单链表,其中的节点应该具备两个属性:val 和 next 。val 是当前节点的值,next 是指向下一个节点的指针/引用。

实现 MyLinkedList 类:

  1. MyLinkedList()初始化 MyLinkedList 对象。
  2. int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效,则返回 -1
  3. void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后,新节点会成为链表的第一个节点。
  4. void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
  5. void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度,那么该节点会被追加到链表的末尾。如果 index 比长度更大,该节点将 不会插入 到链表中。
  6. void deleteAtIndex(int index) 如果下标有效,则删除链表中下标为 index 的节点。

示例:

输入
[“MyLinkedList”, “addAtHead”, “addAtTail”, “addAtIndex”, “get”, “deleteAtIndex”, “get”]
[[], [1], [3], [1, 2], [1], [1], [1]]
输出
[null, null, null, null, 2, null, 3]
解释
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2); // 链表变为 1->2->3
myLinkedList.get(1); // 返回 2
myLinkedList.deleteAtIndex(1); // 现在,链表变为 1->3
myLinkedList.get(1); // 返回 3

来源:力扣707

代码

定义节点类//构造函数使用的是列表初始化

    struct LinkedNode {
        int val;
        LinkedNode* next;
        LinkedNode(int val):val(val), next(nullptr){}//构造函数使用的是列表初始化
    };
  1. MyLinkedList()
    MyLinkedList() {
        _dummyHead = new LinkedNode(0); //虚拟头节点
        _size = 0;//链表长度
    }
    ...
    ...
    private:
      int _size;
      LinkedNode* _dummyHead;
  1. int get(int index) //查询节点一般cur都是指向head(当前节点)
int get(int index) {
        if (index > (_size - 1) || index < 0) {
            return -1;
        }
        LinkedNode* cur = _dummyHead->next;//查询节点一般cur都是指向head(当前节点)
        while(index--){ // 如果--index 就会陷入死循环
            cur = cur->next;
        }
        return cur->val;
    }
  1. void addAtHead(int val)
    void addAtHead(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        newNode->next = _dummyHead->next;
        _dummyHead->next = newNode;
        _size++;
    }
  1. void addAtTail(int val) //增删节点一般cur都指向虚拟节点
    void addAtTail(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = _dummyHead;
        while(cur->next != nullptr){//利用尾节点的next指向空判断
            cur = cur->next;
        }
        cur->next = newNode;
        _size++;
    }
  1. void addAtIndex(int index, int val) //增删节点一般cur都指向虚拟节点
    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++;
    }
  1. void deleteAtIndex(int index)//增删节点一般cur都指向虚拟节点
    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--;
    }

来源:代码随想录

移除链表元素

题目

给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。
示例:
算法-设计链表、移除链表元素、反转链表

输入:head = [1,2,6,3,4,5,6], val = 6
输出:[1,2,3,4,5]

来源:力扣203

思路

链表的增删一般创建一个虚拟头节点有助于统一代码。链表中节点的删除需要目标节点的前节点直接指向目标节点的下一个节点,然后delete掉当前节点。

阻碍

1.删除链表节点需要那三个节点?
链表删除需要三个节点的信息,前节点、当前节点、后节点。单向链表无法像数组一样执行双向遍历,所以在链表中当前节点不能是cur,因为前节点无法表示为
cur->pre,故前节点应为cur,当前节点为cur->next,后节点为cur->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 !=nullptr){
            if(cur->next->val==val){
                ListNode* temp=cur->next;
                cur->next=cur->next->next;
                delete temp;
            }
            else{
                cur=cur->next;
            }
            
        }
        head=dummynode->next;
        delete dummynode;
        return head;

    }
};

来源:代码随想录

反转链表

题目

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
示例 :
算法-设计链表、移除链表元素、反转链表

输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]

来源:力扣206

思路

改变链表指向,即可实现反转。一共分四步:①定义移动指针preh和cur②保存节点③改变指针方向④更新pre和cur。

阻碍

  1. pre指针和cur指针的初始化?
    cur用来遍历当前链表,所以初始化为头节点head;因为原来的head要变为尾节点,所以pre初始化为空。

代码

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre=nullptr;
        ListNode* cur=head;
        ListNode* temp;
        while(cur){
            temp=cur->next;
            cur->next=pre;
            pre=cur;
            cur=temp;
        }
        return pre;

    }
};

来源:代码随想录文章来源地址https://www.toymoban.com/news/detail-501654.html

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

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

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

相关文章

  • day 3 | 203.移除链表元素、707.设计链表、206.反转链表

    目录: 链表基础:https://programmercarl.com/链表理论基础.html 题目链接: https://leetcode.cn/problems/remove-linked-list-elements/ 203. 移除链表元素 给你一个链表的头节点  head  和一个整数  val  ,请你删除链表中所有满足  Node.val == val  的节点,并返回  新的头节点  。 自己思路:从头

    2024年02月08日
    浏览(43)
  • Day 3 链表: 203.移除链表元素, 707.设计链表, 206.反转链表

    链接基础,以及链表和数组的区别: 代码随想录 1. 链表类型: 单列表,双列表,循环列表。 单列表: 双列表: 循环列表: 2. 链表的操作 :删除节点,增加节点。 删除节点: 其中对于 普通的节点 删除,就如上图所示,直接让前一个节点的指向下一个节点即可。 但是对于

    2024年02月16日
    浏览(41)
  • Day03|链表01:203.移除链表元素、707.设计链表、206.反转链表

    今天进入链表章节的学习了,也是之前学过的内容,这次争取快速AC。 leetcode链接:https://leetcode.cn/problems/remove-linked-list-elements/ 没什么好说的,这里注意引入了一个虚拟头节点dummy,这样就不用处理需要删除第一个节点的特殊情况。删除时C++需要手动detete。我本来使用free的,

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

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

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

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

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

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

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

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

    2024年02月08日
    浏览(45)
  • 【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日
    浏览(41)
  • 复习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)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包