程序员经验分享-hwhale

LeetCode 解题笔记（四）链表

2023-05-16

文章目录

  • 一、总结
  • 二、题目
    • 237. 删除链表中的节点（2022/03/10）
    • 19. 删除链表的倒数第 N 个结点（2022/03/11）
    • 206. 反转链表（2022/03/18）
    • 21. 合并两个有序链表（2022/03/19）
    • 234.回文链表（2022/03/20）
    • 141. 环形链表（2022/03/21）

总目录:      LeetCode 解题笔记（一）总

一、总结

● 链表的简介：

如果你还不太熟悉链表，下面有关于列表的概要讲述。

有两种常用的列表实现，分别为数组列表和链表。如果我们想在列表中存储值，它们是如何实现的呢？

数组 列表底层是使用数组存储值，我们可以通过索引在 O(1) 的时间访问列表任何位置的值，这是由基于内存寻址的方式。

链表 存储的是称为节点的对象，每个节点保存一个值和指向下一个节点的指针。访问某个特定索引的节点需要O(n) 的时间，因为要通过指针获取到下一个位置的节点。
 

● 链表中方法总结：

① 常用的方法：
● 暴力破解，常用手段
● 栈stack：先进后出， 适合链表
● 哈希表：用 unordered_map 或 unordered_set
● 双指针（快慢指针）
● 递归：有重复公式的，先进后出

② 增加哑结点。考虑如果需要删除头节点的话，这时需要新增一个哑节点dummy ，它下一个节点为 head；
增加： ListNode *dummy = new ListNode(0, head);
删除： delete dummy;

③ 链表中循环 while 比 for 好用

二、题目

237. 删除链表中的节点（2022/03/10）

链接： 237. 删除链表中的节点

标签：链表

题目：
在这里插入图片描述

class Solution {
public:
    void deleteNode(ListNode* node) {
        //4 5 1 9  变为 4 1 9 
        //本来要删除第二个，现只需要删除第三个就好，把三个的值要复制给第二个
        node->val = node->next->val;
        node->next = node->next->next;    
    }
};

19. 删除链表的倒数第 N 个结点（2022/03/11）

19. 删除链表的倒数第 N 个结点

题目：
在这里插入图片描述

● 方法一：计算链表长度（我的错误答案：）

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        //只有一个的
        if(head->next == nullptr) 
            return nullptr;

        //遍历求n个节点
        int sum = 0;
        for(ListNode * node = head; node->next != nullptr; node = node->next) {
            sum++;
        }
        sum++;     //2

        ListNode * node2 = head;
        int i = 1;

        while(i < sum-n) {   //sum = 5    n=2    //0 1 2    3
            node2 = node2->next;
            i++;            //加三次就去了4那里了  只需要加两次 
        }
        if(i == sum) {
            node2->next = nullptr;
        } else {
            node2->next = node2->next->next;
        }

        return head;
    }
};

在这里插入图片描述
思路是没有问题的，以下几点得注意：
① 考虑如果删除了头节点，所以需要新增一个哑节点dummy ，它下一个节点为 head；
② 判断链表长度的时候应判断，当前链表 node，而不是 node->next(); 用 while 比 for 好
③ 删除哑结点可以直接：delete dummy;

看了参考答案后，修改上面的：

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        //只有一个的
        if(head->next == nullptr)   return nullptr;

        //遍历求n个节点
        int sum = 0;
        for(ListNode * node = head; node != nullptr; node = node->next) {
            sum++;   //4
        }

        //新增一个空的节点，dummy 指向head
        ListNode *dummy = new ListNode(0, head);
        ListNode * node = dummy;  //当前节点
        int i = 0;

        while(i < sum-n) {   //sum=5 n=1 i<4     //0 1 2 3 4  可以执行四次
            node = node->next;
            i++;           
        }
        node->next = node->next->next;      //如果为最后一个，那么 node->next->next = null 不需要额外判断了
        return dummy->next;
    }
};

● 方法二：栈 stack; 先进后出 

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        stack<ListNode *> stk;
        ListNode *cur = dummy;
        while(cur) {
            stk.push(cur);
            cur = cur->next;
        }
        for(int i=0; i<n; i++) {
            stk.pop();
        }
        ListNode* prev = stk.top();
        prev->next = prev->next->next;
        ListNode* ans = dummy->next;
        delete dummy;
        return ans;
    }
};

● 方法三：双指针

快指针比慢指针快了 2 个！ 画图一目了然

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* first = head;
        ListNode* dummy = new ListNode(0, head);
        ListNode* second = dummy;
        for(int i=0; i<n; i++) {
            first = first->next;
        }
        while(first) {
            first = first->next;
            second = second->next;
        }
        second->next = second->next->next;
        ListNode* ans = dummy->next;
        delete dummy;
        return ans;
    }
};

206. 反转链表（2022/03/18）

● 链接： 206. 反转链表

● 标签： 链表、递归

● 题目：
在这里插入图片描述
● 方法一：官方答案

假设链表为 1→2→3→∅，我们想要把它改成 ∅←1←2←3。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {

        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr) {
            //先修改 curr->next; 并且先要保存curr->next, 很奇妙
            ListNode* next = curr->next;
            curr->next = prev;
            
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

21. 合并两个有序链表（2022/03/19）

● 链接： 21. 合并两个有序链表

● 标签： 链表、递归

● 题目：
在这里插入图片描述

● 方法一：通用野蛮法

/**
 * 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* mergeTwoLists(ListNode* list1, ListNode* list2) {

        // ListNode* dummy = new ListNode(0, list1);
        ListNode* listHead = new ListNode(-1);  
        ListNode* cur = listHead;
        while(list1 || list2) {
            //处理空指针
            if(list1 == nullptr) {
                cur->next = list2;
                break;
            }
            if(list2 == nullptr) {
                cur->next = list1;
                break;
            }

            if(list1->val <= list2->val) {
                cur->next = list1;
                list1 = list1->next;
            }
            else {
                cur->next = list2;
                list2 = list2->next;
            }
            cur = cur->next;   //这个是关键
        }
        
        ListNode* ans = listHead->next;
        delete listHead;
        return ans;
    }
};

● 方法二：递归高级法

递归就是先进后出，和栈一样！

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        //1.递归
        if(list1 == nullptr) return list2;

        if(list2 == nullptr) return list1;

        if(list1->val < list2->val) {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }
        else {
            list2->next = mergeTwoLists(list2->next, list1);
            return list2;
        }
    }
};

234.回文链表（2022/03/20）

● 链接： 234. 回文链表

● 标签： 递归、链表、双指针

● 题目：
在这里插入图片描述

● 我的答案：计算个数，压栈 + 头和栈尾比较

（内存消耗有点大）

/**
 * 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:
    bool isPalindrome(ListNode* head) {
        ///计算个数
        int n = 0;
        ListNode *cur = head;
        stack<ListNode *> stk;
        while(cur) {
            n++;
            stk.push(cur);
            cur = cur->next;
        }

        //判断回文
        for(int i=0; i<n/2; i++) {
            if(head->val == stk.top()->val) {
                stk.pop();                //移除
                head = head->next;
            }
            else {
                return false;
            }
        }
        return true;
    }
};

● 官方答案一：将值复制到数组中后用双指针法

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        vector<int> vals;
        while (head != nullptr) {
            vals.emplace_back(head->val);
            head = head->next;
        }
        for (int i = 0, j = (int)vals.size() - 1; i < j; ++i, --j) {
            if (vals[i] != vals[j]) {
                return false;
            }
        }
        return true;
    }
};

141. 环形链表（2022/03/21）

● 链接： 141. 环形链表

● 标签： 哈希、链表、双指针

● 题目：

在这里插入图片描述

● 我的答案（一）哈希 unordered_set

利用 unordered_set，存入每一个链表，并且遍历，有重复就是环形

class Solution {
public:
    bool hasCycle(ListNode *head) {
        //哈希
        unordered_set<ListNode* > _set;
        while(head) {
			//官方用的 _set.count(head) 似乎更加便捷
            if(_set.find(head) != _set.end()) {  
                return true;
            }
            _set.insert(head);
            head = head->next;
        }
        return false;
    }
};

● 我的答案（二）快慢指针

关键点是考虑临界值！

class Solution {
public:
    bool hasCycle(ListNode *head) {
        //快慢指针
        if(head == nullptr || head->next == nullptr) return false;
        ListNode *fast = head->next;
        ListNode *slow = head;
        //官方的 if 和 while 的条件反过来了，并且不需要判断 slow
        while(fast && fast->next && slow) {
            if(fast == slow)          
                return true;
            fast = fast->next->next;
            slow = slow->next;
        }
        return false;
    }
};
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

LeetCode

解题笔记

LeetCode 解题笔记（四）链表 的相关文章

  • 鱼眼镜头的成像原理到畸变矫正（完整版）

    最近刚接触鱼眼相机 xff0c 发现网上资料还是比较零散的 xff0c 于是把搜罗到的资料汇总梳理了一下 这里推荐大家直接看链接6的论文 xff0c 从成像模型到畸变矫正整个过程讲的比较清楚 xff0c 网上很多版本其实都是根据这两篇论文来

随机推荐

  • STM32通过广和通ADP-L610-Arduino进行TCP/IP通信

    STM32通过广和通L610进行TCP IP通信 一 写在前面 本次参加嵌入式大赛 xff0c 使用了广和通的ADP L610 Arduino板子进行通信 项目要求大概是本地上传数据到服务器 xff0c 服务器接收后发送给客户端 xff0c

  • Visual Studio Code Git版本控制 更改语言成英文

    一 初始化git库 新版vscode只能打开一个文件夹 xff0c 当你打开这个文件夹后 xff0c 再点击左边的git控制按钮 xff0c 就会初始化该文件夹为git工作目录 xff0c 如果已经有git控制 xff0c 则不会改变 在v

  • STM8S003F3 开发环境搭建

    硬件相关 芯片介绍 型号 xff1a STM8S003F3P6 xff0c 用的不是ARM内核 STM32用的是ARM xff0c 而是意法半导体自己生产的高性能8位内核 xff1a STM8AF 主要针对汽车电子应用 xff0c 如 xf

  • 教你写Makefile（很全，含有工作经验的）

    原文 转载文 Makefile 值得一提的是 xff0c 在Makefile中的命令 xff0c 必须要以 Tab 键开始 什么是makefile xff1f 或许很多Winodws的程序员都不知道这个东西 xff0c 因为那些Window

  • 与JWT的不解之缘

    jar xff1a maven lt dependency gt lt groupId gt io jsonwebtoken lt groupId gt lt artifactId gt jjwt lt artifactId gt lt v

  • 连接服务器报错：Key exchange was not finished, connection is closed.

    解决方案 xff1a 在 etc ssh sshd config最后添加如下行内容解决问题 KexAlgorithms diffie hellman group1 sha1 diffie hellman group14 sha1 diffi

  • ros多线程管理

    单线程Spinning ros spin 是最简单的单线程自旋 它会一直调用直到结束 用法 ros spin ros spinOnce 另一个单线程spinning是ros spinOnce 它定期调用等待在那个点上的所有回调 用法 ros

  • （每日一读2019.10.24）一种基于通用优化方法的多传感器全局里程计估计框架（VINS-Fusion）

    参考博文 萌新学VINS Fusion 一 特征跟踪 萌新学VINS Fusion 二 特征跟踪 摘要 精确的状态估计是自主机器人的一个基本问题 为了实现局部精确和全局无漂移状态估计 通常将具有互补特性的多个传感器融合在一起 局部传感器 摄

  • （每日一读2019.10.25）一种基于通用优化方法的多传感器局部里程计估计框架（VINS-Fusion）

    摘要 为了提高机器人的鲁棒性和自主性 越来越多的传感器被安装在机器人上 我们已经看到了不同平台上安装的各种传感器套件 例如地面车辆上的立体摄像机 手机上带有IMU 惯性测量单元 的单目摄像机以及空中机器人上带有IMU的立体摄像机 虽然过去已

  • Gazebo模型下载以及配置--解决Gazebo黑屏原因

    前往ExBot ROS专区下载Gazebo模型 https bitbucket org osrf gazebo models downloads 下载后把文件放在 gazebo下的models文件夹中 span class token fu

  • 相机内外参数以及畸变参数

    关于大佬们的一些见解 下面是引用知乎的一段文字 xff1a 我们从单目视觉说起 平时我们都说要做视觉识别 测量云云 xff0c 然后我们就会去拍照 xff0c 再对数字图像做各种处理 xff0c 颜色处理 灰度化 滤波 边缘检测 霍夫变换

  • cmake学习4--自定义编译选项

    CMake 允许为项目增加编译选项 xff0c 从而可以根据用户的环境和需求选择最合适的编译方案 例如 xff0c 可以将 MathFunctions 库设为一个可选的库 xff0c 如果该选项为 ON xff0c 就使用该库定义的数学函数

  • ROS与C++学习1

    ROS与C 入门教程 构建工作空间 构建Catkin包 搭建开发环境 catkin make 编写简单发布节点和订阅节点 编写简单服务端和客户端 使用类方法作为回调函数 使用Timers类 编写高级的发布器和订阅器 Callbacks和Sp

  • IAR的UI界面优化

    显示行数 Tools Options 点击 Editor Tab size xff1a 设置Tab键占用多少个空格Indent size xff1a 应该是设置过行时缩进多少个空格Insert tab xff1a 选了之后在删除Tab时 x

  • MYNTEYE小觅双目摄像头深度版+VINS测试

    小觅双目深度版性能分析 今年 xff08 18年 xff09 11月9号小觅智能科技的深度版双目相机上市 xff0c 于是我在12月初花了2999软妹币购买了120度视角的相机 其中我比较感兴趣的是 双目 43 惯导 43 结构光 的多传感

  • QT+ROS开发

    Qt Creator for ROS 如果想在Qt上进行ros包的开发和GUI界面开发 建议采用下面的方法 http fumacrom com 1mipW Setup Qt Creator for ROS Setup Ubuntu to a

  • PX4、APM无人机仿真连接QGC地面站记录（udp连接、更改home点等）

    文章目录 一 PX41 gazebo 仿真2 连接地面站3 更改 Home点 二 APM 仿真1 执行仿真指令2 连接地面站3 更改 Home 点 本文仅记录仿真指令 xff0c 搭建安装不在此 一 PX4 首先给飞控源码和子目录权限 sp

  • LeetCode 解题笔记（一）总

    文章目录 一 常用技巧二 常用翻译三 题目x 其他9 回文数 2021 12 0911 盛最多水的容器 2022 01 0515 三数之和 2022 01 14 17 电话号码的字母组合 2022 01 1520 有效的括号 2021 12

  • LeetCode 解题笔记（二）数组篇

    文章目录 一 基础篇26 删除排序数组中的重复 2022 01 16122 买卖股票的最佳时机 II 2022 01 17189 轮转数组 2022 01 18217 存在重复元素 2022 01 19136 只出现一次的数字 2021 1

  • LeetCode 解题笔记（四）链表

    文章目录 一 总结二 题目237 删除链表中的节点 xff08 2022 03 10 xff09 19 删除链表的倒数第 N 个结点 xff08 2022 03 11 xff09 206 反转链表 xff08 2022 03 18 xff0

热门标签