代码随想录day3 | 203.移除链表元素 707.设计链表 206.反转链表

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

一、移除链表元素的思想

直接让前一个节点指向后一个节点即可

两种方法

第一种:直接删除
第二种:头删的时候,直接head=head->next

其实这两种方法都没有做到统一

第三种:虚拟头结点法
这样的话,咱们删除的时候,就是以统一的规则来进行删除啦!
代码随想录day3 | 203.移除链表元素 707.设计链表 206.反转链表,笔试强训,链表,链表反转,设计链表

二、203.移除链表元素

203.移除链表元素
法一:原始删除法

class Solution
{
public:
    ListNode *removeElements(ListNode *head, int val)
    {
        // 头删
        while (head != nullptr && head->val == val)
        {
            ListNode *tmp = head;
            head = head->next;
            delete tmp;
        }
        // 接下来不是头删,正常的中间删除
        ListNode *cur = head;
        while (cur != nullptr && cur->next != nullptr)
        {
            if (cur->next->val == val)
            {
                ListNode *tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp; // 内存释放
            }
            else
            {
                cur = cur->next;
            }
        }
        return head;
    }
};

1、while(head!=nullptr && head->val == val)?

注意使用while 而不是 if ,因为会有特殊情况,持续删除头结点的情况,所以使用外while。

2、if(cur->next->val==val)

我们是使用的cur的next的值来判断是不是我们想要删除的val的。如果我们直接使用cur的值来判断的话,我们是不好来找到当前节点的上一个节点,从而链接起来的。

法二:虚拟头结点法

代码随想录day3 | 203.移除链表元素 707.设计链表 206.反转链表,笔试强训,链表,链表反转,设计链表

class Solution
{
public:
    ListNode *removeElements(ListNode *head, int val)
    {
        // 虚拟头结点来删除
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;
        ListNode *cur = dummy; // 为啥从dummy起始?
        while (cur->next != nullptr)
        {
            if (cur->next->val == val)// 为啥用cur->next->val 作为判断?
            {
                cur->next = cur->next->next;
            }
            else
            {
                cur = cur->next;
            }
        }
        return dummy->next;
    }
};

1、ListNode *cur = dummy; // cur为啥从dummy起始?

而不是cur=head?
我们删除链表元素一定要知道上一个元素的指针是啥,我们删的是cur->next->val。

2、while (cur->next != nullptr)

遍历的时候,我们要判断的是cur->next->val,所以我们while (cur->next != nullptr) 要这么写。

3、if (cur->next->val == val)// 为啥用cur->next->val 作为判断?

我们是使用的cur的next的值来判断是不是我们想要删除的val的。如果我们直接使用cur的值来判断的话,我们是不好来找到当前节点的上一个节点,从而链接起来的。

4、为啥return dummy->next;

因为return head;有可能head已经被删除了。

三、707.设计链表

707.设计链表

统一使用虚拟头结点的方式,让我们的操作统一化。
我们还需要一个虚拟头节点_dummy作为头节点,和一个_size参数保存有效节点数。注意题目下标从0开始。

一定要注意:我们的临时变量定义cur=_dummy,操作的是cur->next,这样我才能方便的增加、删除,这才是对应到我们的第index(或者说第n个节点)。

class MyLinkedList
{
public:
    // 定义链表节点结构体
    struct ListNode
    {
        int val;
        ListNode *next;
        ListNode(int val) : val(val), next(nullptr) {}
    };
    MyLinkedList()
    {
        // 定义虚拟头结点
        _dummy = new ListNode(-1);
        _size = 0;
    }


// 获取到第index个节点数值,如果index是非法数值直接返回-1, 注意index是从0开始的,第0个节点就是头结点
// 注意 index和_size差值为1
    int get(int index)
    {
        if (index > (_size - 1) || index < 0)
        {
            return -1;
        }
        ListNode *cur = _dummy->next; // 从头开始遍历寻找
        // 注意下标从0开始
        while (index)
        {
            cur = cur->next;
            index--;
        }
        return cur->val;
    }

    void addAtHead(int val)
    {
        ListNode *newnode = new ListNode(val);

        // 这两步顺序不能交换
        newnode->next = _dummy->next;
        _dummy->next = newnode;

        _size++;
    }

    void addAtTail(int val)
    {
        ListNode *newnode = new ListNode(val);
        // 找尾
        ListNode *cur = _dummy; // 为啥从dummy开始?
        while (cur->next != nullptr)
        {
            cur = cur->next;
        }
        cur->next = newnode;
        _size++;
    }

	
	// 如果index大于链表的长度,则返回空
    // 如果index小于0,则在头部插入节点
    void addAtIndex(int index, int val)
    {
        if (index > _size)
            return;
        if (index < 0)
            index = 0;
            
        // 一定要找到第index个节点的前驱
        ListNode *newnode = new ListNode(val);
        ListNode *cur = _dummy;
        // 遍历找到第n个节点
        while (index--)
        {
            cur = cur->next;
        }
        // 这下面两步顺序也是不能换的
        newnode->next = cur->next;
        cur->next = newnode;
        _size++;
    }

    void deleteAtIndex(int index)
    {
        if (index < 0 || index >= _size)
        {
            return;
        }
        ListNode *cur = _dummy;
        // 遍历找到第n个节点
        while (index--) // 当index=0时,while循环就不会执行了
        {
            cur = cur->next;
        }
        ListNode *tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        tmp = nullptr;
        _size--;
    }

private:
    int _size;
    ListNode *_dummy;
};

1、头插顺序不能变

代码随想录day3 | 203.移除链表元素 707.设计链表 206.反转链表,笔试强训,链表,链表反转,设计链表

2、addAtTail 中ListNode * cur=_dummy;// 为啥从dummy开始?

因为有可能刚刚开始没有元素,相当于在dummy后插入。

3、注意index与size之间的关系,他们差值为1

四、206.反转链表

206.反转链表
面试中经常出现

双指针法

// 双指针
class Solution
{
public:
    ListNode *reverseList(ListNode *head)
    {
        ListNode *cur = head;
        ListNode *pre = nullptr;
        while (cur != nullptr)
        {
            ListNode *tmp = cur->next;
            cur->next = pre; // 反转操作
            // 下面两步不能换顺序
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
};

1、为啥要这样初始化?

因为这样初始化,直接让咱们的反转后的尾节点直接执行nullptr了。
代码随想录day3 | 203.移除链表元素 707.设计链表 206.反转链表,笔试强训,链表,链表反转,设计链表

2、while( ? ) 循环结束调条件是啥

就是cur为空就结束了,最后一步,不再需要nullptr指向pre了,没有意义。while(cur)就行了。

3、为啥需要每次进入循环都要定义一个tmp临时变量?

因为这样可以方便更新cur,反转后,cur无法后移指向下一个节点,tmp保存cur->next,趁着pre和cur还连着的时候先保存下来,然后就可以赋值了,一定要先移pre,后移动cur。
代码随想录day3 | 203.移除链表元素 707.设计链表 206.反转链表,笔试强训,链表,链表反转,设计链表

递归法

class Solution
{
public:
    // 子函数
    ListNode *reverse(ListNode *cur, ListNode *pre)
    {
        if (cur == nullptr)
            return pre;           // 2.终止条件就是cur指向nullptr
        ListNode *tmp = cur->next;
        cur->next = pre;          // 3.反转操作
        return reverse(tmp, cur); // 4、进入下一层循环(递归) 谁赋值给cur? 谁赋值给pre?
    }

    ListNode *reverseList(ListNode *head)
    {
        return reverse(head, nullptr); // 1.head赋值给cur,nullptr赋值给pre
    }
};

从后往前翻转指针指向 递归

  • 使用递归函数,一直递归到链表的最后一个结点,该结点就是反转后的头结点,记作last
  • 此后,每次函数在返回的过程中,让当前结点的下一个结点的next指针指向当前节点。
  • 同时让当前结点的neat指针指向NULL,从而实现从链表尾部开始的局部反转
  • 当递归函数全部出栈后,链表反转完成。
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 边缘条件判断
        if(head == NULL) return NULL;
        if (head->next == NULL) return head;
        
        // 递归调用,翻转第二个节点开始往后的链表
        ListNode *last = reverseList(head->next);
        // 翻转头节点与第二个节点的指向
        head->next->next = head;
        // 此时的 head 节点为尾节点,next 需要指向 NULL
        head->next = NULL;
        return last;
    }
}; 

代码随想录day3 | 203.移除链表元素 707.设计链表 206.反转链表,笔试强训,链表,链表反转,设计链表文章来源地址https://www.toymoban.com/news/detail-598953.html

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

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

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

相关文章

  • 代码随想录-链表1( 203.移除链表元素、)

    203. 移除链表元素 707. 设计链表 206. 反转链表         自己写的是从后往前去反转,没想到可以从前往后反转的方法,以为地址不连续并且无法根据索引找地址就没办法做,看了双指针方法后才发现如何从前往后反转,其实只要记录每个结点的地址就可以了,还是对链表的

    2024年02月19日
    浏览(48)
  • 【代码随想录 | Leetcode | 第五天】链表 | 移除链表元素 | 设计链表 | 203-707

    欢迎来到小K的Leetcode|代码随想录|专题化专栏,今天将为大家带来移除链表元素和设计链表的分享 ✨ ✨题目链接点这里 给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。 示例 1: 示例 2: 示例 3: 提示: 列表中

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

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

    2024年02月08日
    浏览(47)
  • 代码随想录Day3 | 链表01-leetcode203、707、206

    题目链接:移除链表元素 思路: 链表中元素的添加和删除关键是要 保证不断链且指向关系正确 。对于删除操作,链的修改涉及将待删除元素的前一个元素指向待删除元素的后一个元素,因此在判断当前元素是否需要删除时,要记录当前元素的前后指针。 1.删除头结点时另作

    2024年02月16日
    浏览(68)
  • 代码随想录第三天|链表理论基础,LeetCode203.移除链表元素, LeetCode707.设计链表,LeetCode 206.反转链表

    链表: 链表是一种通过指针串联在一起的线性结构,每一个节点由两部分组成,一个是数据域一个是指针域(存放指向下一个节点的指针),最后一个节点的指针域指向null(空指针的意思)。 链表的入口节点称为链表的头结点也就是head。 链表类型: 1.单链表 单链表中的指

    2024年02月11日
    浏览(53)
  • 代码随想录day1 | 704.二分查找 27.移除元素

    1、循环变量 2、判断条件 当时左闭右闭时,while循环里面的条件,我们可以先假设,有等号即有left=right的情况,例如[1,1]这个区间,那么循环是要进入里面的,所以要取得等号。 判断的时候,nums[mid]tar,那么必然tar不在右半区间,所以right=mid-1 nums[mid]tar,那么必然tar不在左半

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

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

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

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

    2024年02月04日
    浏览(35)
  • 【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)
  • 算法刷题营【Day3】:: 链表篇:单链表结点删除思路:一题辨别哨兵结点的优势(删除有奇效):203. 移除链表元素

    本内容是笔者结合《代码随想录》总结所得,记录学习过程,分享知识! 目录: 1. 开篇例题:203. 移除链表元素 2. 题解参考 - - 2.1 方法一:原表操作(不含哨兵结点) - - 2.2 方法二:虚设哨兵结点辅助法 - - 2.3 方法三:递归法 3. 单链表结点删除思路 4. 方法思路点拨:原表操

    2024年02月06日
    浏览(48)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包