C++数据结构与算法——链表

C++第二阶段——数据结构和算法，之前学过一点点数据结构，当时是基于Python来学习的，现在基于C++查漏补缺，尤其是树的部分。这一部分计划一个月，主要利用代码随想录来学习，刷题使用力扣网站，不定时更新，欢迎关注！

文章目录

  • 一、移除链表元素（力扣203）
  • 二、设计链表（力扣707）
  • 三、翻转链表（力扣206）
  • 四、两两交换链表中的节点 (力扣24)
  • 五、删除链表的倒数第 N 个结点（力扣19）
  • 六、链表相交（力扣面试题02.07链表相交）
  • 七、环形链表Ⅱ（力扣142）

一、移除链表元素（力扣203）

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点
在这里插入图片描述
头结点单独处理

/**
 * 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) {
        // 先判断头结点是不是val，如果是的话，head就后移
        while(head!=NULL && head->val==val){
            ListNode * temp ;
            temp = head;
            head = head->next;
            delete temp;
        }
        // 定义一个指针指向中间过程的结点
        ListNode * cur = head;
        while(cur!=NULL&&cur->next!=NULL){
            if(cur->next->val==val){
                // 删除下一个结点
                ListNode *temp = cur->next;
                cur->next = cur->next->next;
                delete temp;
            }
            else{
                cur = cur->next;
            }
        }
        return head;
    }
};

在这里插入图片描述

虚拟头节点

/**
 * 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 * dummyHead = new ListNode(0); 
        dummyHead->next = head;
        // 定义一个遍历结点
        ListNode *cur = dummyHead;
        while(cur!=NULL&&cur->next!=NULL){
            if(cur->next->val==val){
                ListNode * temp = cur->next;
                cur->next = cur->next->next;
                delete temp;
            }
            else{
                cur = cur->next;
            }

        }
        return dummyHead->next;
    }
};

在这里插入图片描述

二、设计链表（力扣707）

你可以选择使用单链表或者双链表，设计并实现自己的链表。
单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。
如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。
实现 MyLinkedList 类：
MyLinkedList() 初始化 MyLinkedList 对象。
int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
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
提示：
0 <= index, val <= 1000
请不要使用内置的 LinkedList 库。
调用 get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex 的次数不超过 2000 。

// 创建一个结点
class LinkNode{
public:
    LinkNode(int inputVal){
        this->val = inputVal;
    }
    int val;
    LinkNode *next=NULL;
};

class MyLinkedList {
public:// 实现一个单链表
    MyLinkedList() {
    dummyHead= new LinkNode(0);
    size=0; // 获取链表长度
    }
    int get(int index) {
        if(index<0||index>(this->size-1)){
            return -1;
        }
        LinkNode * cur = dummyHead->next;
        while(index--){
            cur = cur->next;
        }
        return cur->val;

    }
    
    void addAtHead(int val) {
        LinkNode * insertNode = new LinkNode(val);
        insertNode->next = dummyHead->next;
        dummyHead->next =insertNode;
        size++;

    }
    
    void addAtTail(int val) {
        // 找到尾部
        LinkNode * cur = dummyHead;
        while(cur!=NULL&&cur->next!=NULL){
            cur = cur->next;
        }
        // 插入
        LinkNode * insertNode = new LinkNode(val);
        cur->next = insertNode;
        insertNode->next = NULL;
        size++;

    }
    
    void addAtIndex(int index, int val) {
        if(index>=this->size+1){
            showLink();
            return;
        }
        else if(index == this->size){
            addAtTail(val);

            return;
        }
        else if(index<=0){
            addAtHead(val);

            return;
        }
        LinkNode * cur = dummyHead;
        while(index--){
            cur = cur->next;
        }
        // 添加
        LinkNode * insertNode = new LinkNode(val);
        insertNode->next = cur->next;
        cur->next = insertNode;
        size++;

    }
    
    void deleteAtIndex(int index) {
        if(index<0||index>(this->size-1)){
            return ;
        }
        LinkNode * cur = dummyHead;
        while(index--){
            cur = cur->next;
        }
        // 删除
        LinkNode * temp = cur->next;
        cur->next = cur->next->next;
        delete temp;
        temp = NULL;
        size--;
    }
    LinkNode * dummyHead= new LinkNode(0);
    int size=0; // 获取链表长度
    void showLink(){
        LinkNode * cur = dummyHead;
        while(cur!=NULL&&cur->next!=NULL){
            cout<<cur->next->val<<" ";
            cur = cur->next;
        }
        cout<<endl;
    }
};

// 6,7,2,0,4,
// 4

/**
 * 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）

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
在这里插入图片描述

双指针,注意先移动pre再移动cur。

/**
 * 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==NULL||head->next==NULL){
            // 只有一个结点
            return head;
        }
        // 定义两个指针，一个指前面的，一指后面的
        ListNode *pre = NULL;
        ListNode *cur = head;
        while(cur!=NULL){
            // 用一个值去接收cur
            ListNode *temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }

};

在这里插入图片描述
另外一种通过递归的方式反转链表，等学到递归再补上

四、两两交换链表中的节点 (力扣24)

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
在这里插入图片描述

每两个交换一次，需要找到交换之前的节点。注意交换实的逻辑，对于不变量需要提前保存信息。

/**
 * 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* swapPairs(ListNode* head) {
        if(head==NULL||head->next==NULL){
            return head;
        }
        // 创建一个虚拟头结点
        ListNode * dummyNode = new ListNode(0);
        dummyNode->next =head;
        ListNode * cur = dummyNode;
        while(cur->next!=NULL&&cur->next->next!=NULL){
            ListNode * a = cur->next;
            ListNode * b= cur->next->next->next;
            cur->next = cur->next->next;
            cur->next->next = a;
            a->next = b;
            cur = cur->next->next;
        }
        return dummyNode->next;
    }
};

在这里插入图片描述

五、删除链表的倒数第 N 个结点（力扣19）

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
在这里插入图片描述

双指针的经典题目，快指针先走n个，快慢指针再同时走，当快指针下一个为NULL时，慢指针下一个即为要删除的元素

/**
 * 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* removeNthFromEnd(ListNode* head, int n) {
        if (head==NULL){
            return head;
        }

        ListNode * dummyNode = new ListNode(0);
        dummyNode->next = head;
        // 使用快慢指针
        ListNode* fast = dummyNode;
        ListNode* slow = dummyNode;
        while(n--){
            // 快指针先走n个
            fast = fast->next;
        }
        while(fast!=NULL&&fast->next!=NULL){
            fast = fast->next;
            slow = slow->next;
        }
        // 删除元素
        ListNode * temp = slow->next;
        slow->next = slow->next->next;
        delete temp; // 删除
        return dummyNode->next;
    }
};

在这里插入图片描述

六、链表相交（力扣面试题02.07链表相交）

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
在这里插入图片描述

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        // 实际上是找相等的结点，不是值相等，而是 是同一个结点
        // 将两个链表右对齐
        // 求两个链表的长度
        if(headA==NULL||headB==NULL){
            return NULL;
        }
        int lenA =1;
        int lenB =1;
        ListNode * curA = headA;
        ListNode * curB = headB;
        while(curA->next!=NULL){
            lenA++;
            curA = curA->next;
        }
        while(curB->next!=NULL){
            lenB++;
            curB = curB->next;
        }
        // 找最短的链表
        int minLen =min(lenA,lenB);
        // AB需要移动的长度
        int needA= lenA-minLen;
        int needB = lenB - minLen;
        // 右对齐两个节点
        while(needA--){
            headA = headA->next;
        }
        while(needB--){
            headB = headB->next;
        }
        // 比较之后的链表是否相同
        while(headA!=NULL||headB!=NULL){
            if(headA== headB){
                return headA;
            }
            else{
                headA = headA->next;
                headB = headB ->next;
            }
        }
        return NULL;
    }
};

七、环形链表Ⅱ（力扣142）

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
在这里插入图片描述

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        // 用一个map记录访问过的地址，不断将地址放入map，如果某次map的长度没有发生变化，说明入环了
        map<ListNode *,ListNode *> addmap;
        if(head==NULL){
            return NULL;
        }
        // 创建虚拟头结点
        ListNode * dummyHead = new ListNode(0);
        dummyHead->next = head;
        // 遍历
        ListNode * cur = dummyHead;
        while(cur!=NULL){
            // 记录之前的size
            int firstSize = addmap.size();
            addmap.insert(make_pair(cur->next,cur->next));
            int endSize = addmap.size();
            if(endSize==firstSize){
                // 没有发生变化，说明已经入环
                return addmap[cur->next];
            }
            else{
                cur = cur->next;
            }
            
        }
        return NULL;

    }
};

在这里插入图片描述
使用map存储每个结点的next，如果map存完之后长度没有变，那么说明进入环了，map中存储的值即为要返回的索引值。
使用双指针

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode * first = head;
        ListNode * slow = head;
        while(first!=NULL&&first->next!=NULL){
            first = first->next->next;
            slow = slow->next;
            if(first==slow){
                // 此时相遇
                ListNode * index1 = first;
                ListNode * index2 = head;
                // 找入环口
                while(index1!=index2){
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index1;
            }
        }
        return NULL;

    }
};

在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/361628.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

推特账号被冻结怎么办？检查IP是否正常

推特账号被冻结怎么办？检查IP是否正常

Twitter 拥有庞大的用户群和日常内容流&#xff0c;是沟通、网络和营销的重要平台。然而&#xff0c;处理其限制和潜在的帐户问题可能很棘手。有许多跨境社媒小伙伴反馈&#xff0c;账号无故被冻结&#xff0c;导致内容与客户尽失&#xff01;其实除了账户养号、被举报、广告信…
阅读更多...
重磅！讯飞星火V3.5发布，携手35万生态开发者，赋能千行百业

重磅！讯飞星火V3.5发布，携手35万生态开发者，赋能千行百业

今天的通用人工智能必将像PC和互联网的诞生一样&#xff0c;深刻改变人类生产生活方式。2023年&#xff0c;大模型的基础研究和应用风起云涌。2024年&#xff0c;国内大模型距国际顶尖技术追平了多少&#xff1f;大模型在哪些领域产生了效益&#xff1f; 1月30日&#xff0c;讯…
阅读更多...
前端工程\模块化

前端工程\模块化

前端工程\模块化&#x1f3ed; 本篇文章&#xff0c;学习记录于&#xff1a;尚硅谷&#x1f3a2;&#xff0c;紧接前文&#xff1a;邂逅Node.JS的那一夜→博客 无论是前端、后端、甚至非编程领域都有模块化的概念&#xff0c;只是不同的领域叫法不同&#xff0c;不过&#xf…
阅读更多...
【WPF.NET开发】优化性能：图形呈现层

【WPF.NET开发】优化性能：图形呈现层

本文内容 图形硬件呈现层定义其他资源 呈现层为运行 WPF 应用程序的设备定义图形硬件功能和性能级别。 1、图形硬件 对呈现层级别影响最大的图形硬件功能包括&#xff1a; 视频 RAM - 图形硬件中的视频内存量决定了可用于合成图形的缓冲区大小和数量。 像素着色器 - 像素着…
阅读更多...
【升级openssl1.1.1t报错libssl.so.1.1: cannot open shared object file】

【升级openssl1.1.1t报错libssl.so.1.1: cannot open shared object file】

升级openssl报错&#xff1a; openssl vesion openssl: error while loading shared libraries: libssl.so.1.1: cannot open shared object file: No such file or directory 编译安装openssl1.1.1t当执行openssl version的时候&#xff0c;报上述错误&#xff0c;将编译到的…
阅读更多...
OCP NVME SSD规范解读-8.SMART日志要求-4

OCP NVME SSD规范解读-8.SMART日志要求-4

SMART-21&#xff1a;这段描述解释了一个与设备内部I/O操作非对齐相关的计数器功能。该计数器记录的是由NVMe SSD执行的、起始地址未按照设备内部间接寻址单元&#xff08;IU&#xff0c;Indirection Unit&#xff09;大小进行对齐的写入I/O操作数量。 “Alignment”指的是每次…
阅读更多...
2014年苏州大学837复试机试C/C++

2014年苏州大学837复试机试C/C++

2014年苏州大学复试机试 要求 要求用C/C编程&#xff1b;对程序中必要的地方进行注释。上机规则 请在电脑桌面上新建一个文件夹文件夹名为考试姓名&#xff08;中文&#xff09;&#xff1b;考试完毕后&#xff0c;将所编写的文件放在上述文件中。 第一题&#xff08;20分&…
阅读更多...
使用ffmpeg madiamtx制作一个rtsp源

使用ffmpeg madiamtx制作一个rtsp源

有很多人在跑rtsp解码的demo的时候, 苦于找不到一个可以拉流的源, 这里说一个简单的方法. 使用mediamtx, 加ffmpeg加mp4文件方式, 模拟一个rtsp的源. 基本架构就是这样. 在PC上, 这里说的PC可以是远程的服务器, 也可以是你的开发用的windows, 都行. 把mediamtx, 在pc上跑起来 …
阅读更多...
如何有效避免市场恐慌性抛售？

如何有效避免市场恐慌性抛售？

布雷特斯坦伯格是一位备受尊敬的交易心理导师&#xff0c;曾担任华尔街多家顶级培训机构的心理导师&#xff0c;指导交易员们如何应对心理挑战。作为一名心理学教授和资深交易员&#xff0c;他对交易心理的理解远超常人。人们普遍认为&#xff0c;要想在交易领域取得成功&#…
阅读更多...
BUUCTF-Real-[PHP]XXE

BUUCTF-Real-[PHP]XXE

目录 1、原理 2、XXE漏洞产生的原因 3、开始复现 paylaod 复现 4、flag 1、原理 XML数据在传输过程中&#xff0c;攻击者强制XML解析器去访问攻击者指定的资源内容&#xff08;本地/远程&#xff09;&#xff0c;外部实体声明关键字SYSTEM会令XML解析器读取数据&#xf…
阅读更多...
基于SpringBoot的高校社团管理系统

基于SpringBoot的高校社团管理系统

末尾获取源码作者介绍&#xff1a;大家好&#xff0c;我是何时&#xff0c;本人4年开发经验&#xff0c;专注定制项目开发 更多项目&#xff1a;CSDN主页YAML 我欲乘风归去 又恐琼楼玉宇 高处不胜寒 -苏轼 目录 一、项目简介 二、开发技术与环境配置 2.1 SpringBoot框架 2…
阅读更多...
sqlmap的使用

sqlmap的使用

2024.1.31 sqlmap支持五种不同的注入模式&#xff1a; 1、布尔盲注2、时间盲注3、报错注入4、联合注入5、堆叠注入 检测注入 GET请求的基本格式 ​python sqlmap.py -u <测试网址> Ps:不知道为什么我的sqlmap使用时前面要加python&#xff0c;而大部分其他教程没提到…
阅读更多...
Maven简述

Maven简述

Maven是用于管理和构建Java项目的工具&#xff0c;提供了一套标准化的项目结构&#xff0c;提供了一套标准化的构建流程&#xff0c;提供了一套依赖管理机制&#xff0c;通过Maven使得所有IDE构建的项目结构完全一样&#xff0c;让项目可以通用。 项目名称下分为src 和 pom.xm…
阅读更多...
河南省考后天网上确认，请提前准备证件照哦

河南省考后天网上确认，请提前准备证件照哦

✔报名时间&#xff1a;2024年1月18号一1月24号 ✔报名确认和缴费&#xff1a;2024年1月 31号一2月4号 ✔准考证打印&#xff1a;2024年3月12号一3月17号 ✔笔试时间&#xff1a;2024年3月16日-2024年3月17日。 ✔面试时间&#xff1a;面试时间拟安排在2024年5月中旬 报名网址&…
阅读更多...
【Pwn | CTF】BUUCTF test_your_nc1

【Pwn | CTF】BUUCTF test_your_nc1

天命&#xff1a;时隔两年&#xff0c;又杀回了pwn这里 拿到题目的提示&#xff0c;测试你的nc工具 这题直接连接就可以了&#xff0c;windows装了nc工具&#xff0c;直接耍 nc node5.buuoj.cn 28930 下面给一点nc命令的解释&#xff0c;文心一言得出来的 nc命令是一个用于网…
阅读更多...
CTF-WEB的入门真题讲解

CTF-WEB的入门真题讲解

EzLogin 第一眼看到这个题目我想着用SQL注入 但是我们先看看具体的情况 我们随便输入admin和密码发现他提升密码不正确 我们查看源代码 发现有二个不一样的第一个是base64 意思I hava no sql 第二个可以看出来是16进制转化为weak通过发现是个弱口令 canyouaccess 如果…
阅读更多...
[349. 两个数组的交集]（C语言）（两种解法：双指针+排序，哈希）

[349. 两个数组的交集]（C语言）（两种解法：双指针+排序，哈希）

✨欢迎来到脑子不好的小菜鸟的文章✨ &#x1f388;创作不易&#xff0c;麻烦点点赞哦&#x1f388; 所属专栏&#xff1a;刷题 我的主页&#xff1a;脑子不好的小菜鸟 文章特点&#xff1a;关键点和步骤讲解放在 代码相应位置 前提&#xff1a; 看本文章之前&#xff0c;建…
阅读更多...
iOS开发Xcode中的ld64和-ld_classic是什么意思

iOS开发Xcode中的ld64和-ld_classic是什么意思

在iOS应用程序开发中&#xff0c;Xcode是一款广泛使用的集成开发环境&#xff08;IDE&#xff09;&#xff0c;而链接器是构建应用程序的关键组成部分之一。在Xcode中&#xff0c;我们常常会遇到两个重要的概念&#xff1a;ld64和-ld_classic。它们分别代表了默认链接器和经典链…
阅读更多...
Linux文本三剑客---awk经典案例

Linux文本三剑客---awk经典案例

awk&#xff08;是一种处理文本文件的应用程序&#xff0c;它依次处理文件的每一行&#xff0c;并读取里面的每一个字段。&#xff09; awk 包含几个特殊的内建变量&#xff08;可直接用&#xff09;如下所示&#xff1a; 1、获取根分区剩余大小 #可以使用df -h命令来查看所有…
阅读更多...
OceanBase与新加坡南洋理工大学合作，推进机器学习与数据库技术融合

OceanBase与新加坡南洋理工大学合作，推进机器学习与数据库技术融合

1月31日&#xff0c;OceanBase和新加坡南洋理工大学&#xff08;以下简称“南洋理工大学”&#xff09;签署合作协议&#xff0c;探索数据库智能化的技术创新。合作将以OceanBase 4.0 小鱼&#xff08;Paetica&#xff09;为研究基础&#xff0c;推进机器学习与数据库技术融合。…
阅读更多...
最新文章

Copyright @ 2022~2023