LeetCode---链表

203. 移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

 代码示例1：(直接使用原来的链表来进行移除节点操作)

//时间复杂度: O(n)
//空间复杂度: O(1)
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // 删除头结点
        while (head != NULL && head->val == val) { // 注意这里不是if
            ListNode* tmp = head;
            head = head->next;
            delete tmp;
        }

        // 删除非头结点
        ListNode* cur = head;
        while (cur != NULL && cur->next!= NULL) {
            if (cur->next->val == val) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            } 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) {}
 * };
 */

代码示例2：(设置一个虚拟头结点在进行移除节点操作) 

//时间复杂度: O(n)
//空间复杂度: O(1)
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
        dummyHead->next = head; // 将虚拟头结点指向head，这样方便后面做删除操作
        ListNode* cur = dummyHead;
        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 = dummyHead->next;
        delete dummyHead;
        return head;
    }
};

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 的节点

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

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

代码示例： 

//时间复杂度: 涉及 index 的相关操作为 O(index), 其余为 O(1)
//空间复杂度: O(n)
class MyLinkedList {
public:
    // 定义链表节点结构体
    struct LinkedNode {
        int val;
        LinkedNode* next;
        LinkedNode(int val):val(val), next(nullptr){}
    };

    // 初始化链表
    MyLinkedList() {
        _dummyHead = new LinkedNode(0); // 这里定义的头结点 是一个虚拟头结点，而不是真正的链表头结点
        _size = 0;
    }

    // 获取到第index个节点数值，如果index是非法数值直接返回-1， 注意index是从0开始的，第0个节点就是头结点
    int get(int index) {
        if (index > (_size - 1) || index < 0) {
            return -1;
        }
        LinkedNode* cur = _dummyHead->next;
        while(index--){ // 如果--index 就会陷入死循环
            cur = cur->next;
        }
        return cur->val;
    }

    // 在链表最前面插入一个节点，插入完成后，新插入的节点为链表的新的头结点
    void addAtHead(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        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++;
    }

    // 在第index个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
    // 如果index 等于链表的长度，则说明是新插入的节点为链表的尾结点
    // 如果index大于链表的长度，则返回空
    // 如果index小于0，则在头部插入节点
    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++;
    }

    // 删除第index个节点，如果index 大于等于链表的长度，直接return，注意index是从0开始的
    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--;
    }

    // 打印链表
    void printLinkedList() {
        LinkedNode* cur = _dummyHead;
        while (cur->next != nullptr) {
            cout << cur->next->val << " ";
            cur = cur->next;
        }
        cout << endl;
    }
private:
    int _size;
    LinkedNode* _dummyHead;
};

206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

 代码示例1：（双指针法） 

//时间复杂度: O(n)
//空间复杂度: O(1)
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* temp; // 保存cur的下一个节点
        ListNode* cur = head;
        ListNode* pre = NULL;
        while(cur) {
            temp = cur->next;  // 保存一下 cur的下一个节点，因为接下来要改变cur->next
            cur->next = pre; // 翻转操作
            // 更新pre 和 cur指针
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};

代码示例2：（递归法） 

//时间复杂度: O(n), 要递归处理链表的每个节点
//空间复杂度: O(n), 递归调用了 n 层栈空间
class Solution {
public:
    ListNode* reverse(ListNode* pre,ListNode* cur){
        if(cur == NULL) return pre;
        ListNode* temp = cur->next;
        cur->next = pre;
        // 可以和双指针法的代码进行对比，如下递归的写法，其实就是做了这两步
        // pre = cur;
        // cur = temp;
        return reverse(cur,temp);
    }
    ListNode* reverseList(ListNode* head) {
        // 和双指针法初始化是一样的逻辑
        // ListNode* cur = head;
        // ListNode* pre = NULL;
        return reverse(NULL, head);
    }

};

24. 两两交换链表中的节点 

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

代码示例： 

//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
        dummyHead->next = head; // 将虚拟头结点指向head，这样方便后面做删除操作
        ListNode* cur = dummyHead;
        while(cur->next != nullptr && cur->next->next != nullptr) {
            ListNode* tmp = cur->next; // 记录临时节点
            ListNode* tmp1 = cur->next->next->next; // 记录临时节点

            cur->next = cur->next->next;    // 步骤一
            cur->next->next = tmp;          // 步骤二
            tmp->next = tmp1;   // 步骤三

            cur = cur->next->next; // cur移动两位，准备下一轮交换
        }
        ListNode* result = dummyHead->next;
        delete dummyHead;
        return result;
    }
};

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

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

代码示例：

//时间复杂度: O(n)
//空间复杂度: O(1)
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* slow = dummyHead;
        ListNode* fast = dummyHead;
        while(n-- && fast != NULL) {
            fast = fast->next;
        }
        fast = fast->next; // fast再提前走一步，因为需要让slow指向删除节点的上一个节点
        while (fast != NULL) {
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next; 
        
        // ListNode *tmp = slow->next;  C++释放内存的逻辑
        // slow->next = tmp->next;
        // delete tmp;
        
        return dummyHead->next;
    }
};

 142. 环形链表II

给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

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

不允许修改 链表。

代码示例： 

//时间复杂度: O(n)，快慢指针相遇前，指针走的次数小于链表长度，快慢指针相遇后，两个index指针走的次数也小于链表长度，总体为走的次数小于 2n
//空间复杂度: O(1)

/**
 * 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* fast = head;
        ListNode* slow = head;
        while(fast != NULL && fast->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
            // 快慢指针相遇，此时从head 和 相遇点，同时查找直至相遇
            if (slow == fast) {
                ListNode* index1 = fast;
                ListNode* index2 = head;
                while (index1 != index2) {
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index2; // 返回环的入口
            }
        }
        return NULL;
    }
};

83. 删除排序链表中的重复元素

给定一个已排序的链表的头 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* deleteDuplicates(ListNode* head) {
        if(head == NULL){
            return NULL;
        }
        struct ListNode *node = head;
        while(node->next != NULL){
            if (node->val == node->next->val){
                node->next = node->next->next;//删除重复数据
            }else{
                node = node->next;//值不相等，则向后移一位
            }
        } 
        return head;
    }
};

61. 旋转链表

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

代码示例： 

/**
 * 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* rotateRight(ListNode* head, int k) {
        if(head == NULL || k == 0)  return head;
        int len = 1;
        struct ListNode *node = head;
        while(node->next != NULL){//计算链表长度
            node = node->next;
            len++;
        }

        if(len == k)    return head;  //链表长度和K相等时最终还是原链表

        node->next = head;//将链表变成循环链表,后面再切割
        int i = len - k % len;    //计算头节点的最终位置   
        
        node = head;//将 node 初始化为 head，表示从链表的头节点开始遍历
        while(--i){//每次循环前，先将 i 减 1，然后检查 i 是否为零，如果 i 不是零，则进入循环体。
            node = node ->next;//将 node 指针移动到下一个节点
        }
        head = node->next;//找到新的头结点
        node->next = NULL;//切断尾部与头部
        return head;//返回新的头结点
    }            
};

  

参考如下：

代码随想录

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

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

相关文章

FANUC机器人点位IO监控指令TC_ONLINE

FANUC机器人点位IO监控指令TC_ONLINE

一、系统变量中打开该指令 在示教器系统变量页面中找到其中的MIX_LOGIC变量&#xff0c;点击enter进入变量设置页面 找到其中的USE_TCOL变量将其中的值改为true 即可在IO显示页面中找到TC_ONLINE的监控选项 在显示页面中也可找到其中的监控条件 二、在点位指令中添加点逻辑指令…
阅读更多...
内网安全--隧道技术-MSF上线本地

内网安全--隧道技术-MSF上线本地

免责声明:本文仅做技术交流与学习... 不得不说,小白最近也是用上了viper,这里要特别感谢一下my bro 北岭敲键盘的荒漠猫 MSF--viper: --生成马子-->上线 --进入meterpreter. 1-查看路由,添加路由. 查看路由信息 : run autoroute -p run post/multi/manage/autoroute 添加…
阅读更多...
电脑卡顿---WINDOWS任何关闭应用开机自启动

电脑卡顿---WINDOWS任何关闭应用开机自启动

打开windows11的控制面板&#xff0c;点击应用&#xff0c;点击启动 如下图圈出来的地方就是开机自启动的开关按键。
阅读更多...
Elasticsearch8.13.4版本的Docker启动关闭HTTPS

Elasticsearch8.13.4版本的Docker启动关闭HTTPS

博主环境是&#xff1a; 开发环境&#xff1a;SpringbootElasticSearch客户端对应的starter 2.6.3版本 maven配置 <!-- ElasticSearch --><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-elas…
阅读更多...
嵌入式UI开发-lvgl+wsl2+vscode系列：4、动画（Animations）

嵌入式UI开发-lvgl+wsl2+vscode系列：4、动画（Animations）

文章目录 一、前言二、动画示例1、示例1&#xff08;基础按钮label的组合动画&#xff09;2、示例2&#xff08;回放效果动画&#xff09;3、示例3&#xff08;贝塞尔曲线3动画&#xff09;4、示例4&#xff08;动画时间轴&#xff09; 三、最后 一、前言 接下来我们进行动画的…
阅读更多...
Go 使用 RabbitMQ---------------之一

Go 使用 RabbitMQ---------------之一

RabbitMQ 是一种消息代理。消息代理的主要目的是接收、存储并转发消息。在复杂的系统设计和微服务架构中，RabbitMQ 经常被用作中间件来处理和转发系统之间的消息，以确保数据的一致性和可靠性。正是因为提供了可靠的消息机制、跟踪机制和灵活的消息路由，常常被用于排队算法、…
阅读更多...
【做一道算一道】力扣332.重新安排行程

【做一道算一道】力扣332.重新安排行程

332.重新安排行程 给定一个机票的字符串二维数组 [from, to]&#xff0c;子数组中的两个成员分别表示飞机出发和降落的机场地点&#xff0c;对该行程进行重新规划排序。所有这些机票都属于一个从 JFK&#xff08;肯尼迪国际机场&#xff09;出发的先生&#xff0c;所以该行程必…
阅读更多...
区间相交-435. 无重叠区间，56. 合并区间

区间相交-435. 无重叠区间，56. 合并区间

题目连接及描述 435. 无重叠区间 - 力扣&#xff08;LeetCode&#xff09; 56. 合并区间 - 力扣&#xff08;LeetCode&#xff09; 题目分析 二维数组&#xff0c;数组中每个元素为大小为2的一维数组&#xff0c;求移除区间的最小数量&#xff0c;使剩余区间互不重叠。今天写…
阅读更多...
Golang原生http实现中间件

Golang原生http实现中间件

Golang原生http实现中间件 中间件&#xff08;middleware&#xff09;&#xff1a;常被用来做认证校验、审计等 大家常用的Iris、Gin等web框架&#xff0c;都包含了中间件逻辑。但有时我们引入该框架显得较为繁重&#xff0c;本文将介绍通过golang原生http来实现中间件操作。全…
阅读更多...
小熊家务帮day5 客户管理模块1 （小程序认证，手机验证码认证等）

小熊家务帮day5 客户管理模块1 （小程序认证，手机验证码认证等）

客户管理模块 1.认证模块1.1 认证方式介绍1.1.1 小程序认证1.1.2 手机验证码登录1.1.3 账号密码认证 1.2 小程序认证1.2.1 小程序申请1.2.2 创建客户后端工程jzo2o-customer1.2.3 开发部署前端1.2.4 小程序认证流程1.2.4.1 customer小程序认证接口设计Controller层Service层调用…
阅读更多...
使用Spring Boot编写的小项目

使用Spring Boot编写的小项目

加法计算器 前端代码 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>Document</title> <…
阅读更多...
杭州威雅学校：在学业与生活平衡中找到更好的自己

杭州威雅学校：在学业与生活平衡中找到更好的自己

进入威雅杭州校园&#xff0c; 沿湖边小道步行约5分钟&#xff0c; 四栋寄宿学院与教学区隔湖相望&#xff0c; 威雅人更喜欢叫他们&#xff1a; 「Cavell」&「Dove」 「Elgar」&「Hawking」 提起「寄宿制」&#xff0c;人们本能地会把它和「住校」划等号。 这种…
阅读更多...
【官方指南】3ds Max中纹理贴图问题及正确解决方案

【官方指南】3ds Max中纹理贴图问题及正确解决方案

在使用3ds Max进行设计和制作时&#xff0c;纹理贴图是一个非常重要的环节。然而&#xff0c;许多用户在使用过程中常会遇到各种纹理贴图问题。为此&#xff0c;Autodesk官方提供了一些有效的解决方案&#xff0c;可以解决90%的纹理贴图难题。这里小编都帮大家整理好了&#xf…
阅读更多...
【加密与解密（第四版）】第十二章笔记

【加密与解密（第四版）】第十二章笔记

第十二章 注入技术 12.1 DLL注入方法 在通常情况下&#xff0c;程序加载 DLL的时机主要有以下3个&#xff1a;一是在进程创建阶段加载输入表中的DLL&#xff0c;即俗称的“静态输人”;二是通过调用 LoadLibrary(Ex)主动加载&#xff0c;称为“动态加载”&#xff1b;三是由于系…
阅读更多...
网络原理-------TCP协议

网络原理-------TCP协议

文章目录 TCP协议TCP协议段格式TCP原理确认应答机制 (安全机制)超时重传机制 (安全机制)连接管理机制 (安全机制)滑动窗口 (效率机制)流量控制 (安全机制)拥塞控制 (安全机制)延迟应答 (效率机制)捎带应答 (效率机制) 基于TCP的应用层协议 TCP协议 TCP, 即 Transmission Contr…
阅读更多...
The Sandbox DAO：投票决定元宇宙的未来！

The Sandbox DAO：投票决定元宇宙的未来！

赋予用户治理权&#xff0c;打造由社群运营的开放式数码国度 随着The Sandbox DAO的启动&#xff0c;我们邀请全球社群——这个新数字国度的公民们——提出建议并参与治理&#xff0c;共同塑造开放元宇宙的未来。 介绍 在The Sandbox&#xff0c;我们正在建立一个开放的元宇宙…
阅读更多...
数据恢复与取证软件: WinHex 与 X-Ways Forensics 不同许可证功能区别

数据恢复与取证软件: WinHex 与 X-Ways Forensics 不同许可证功能区别

天津鸿萌科贸发展有限公司从事数据安全业务20余年&#xff0c;在数据恢复、数据取证、数据备份等领域有丰富的案例经验、专业技术及良好的行业口碑。同时&#xff0c;公司面向取证机构及数据恢复公司&#xff0c;提供数据恢复实验室建设方案&#xff0c;包含数据恢复硬件设备及…
阅读更多...
【C++初阶】--- C++入门（中）

【C++初阶】--- C++入门（中）

目录 一、缺省参数1.1 缺省参数概念1.2 缺省参数分类 二、函数重载2.1 函数重载概念2.2 C支持函数重载的原理 --- 名字修饰 三、引用3.1 引用概念3.2 引用特性3.3 常引用3.4 使用场景3.5 引用和指针的区别 一、缺省参数 1.1 缺省参数概念 缺省参数是声明或定义函数时为函数的…
阅读更多...
003 仿muduo实现高性能服务器组件_前置知识

003 仿muduo实现高性能服务器组件_前置知识

​&#x1f308;个人主页&#xff1a;Fan_558 &#x1f525; 系列专栏&#xff1a;仿muduo &#x1f339;关注我&#x1f4aa;&#x1f3fb;带你学更多知识 文章目录 前言时间轮timewheel设计正则表达式介绍&#xff08;了解知道怎么使用&#xff09;通用型any容器的实现 小结 …
阅读更多...
5-26作业

5-26作业

网络聊天室 服务器&#xff1a; 1 #include <myhead.h>2 int main(int argc, const char *argv[])3 {4 if(argc!3)5 {6 printf("请输入IP和端口号\n");7 return -1;8 }9 int sfd socket(AF_INET, SOCK_DGRAM, 0);10 if(…
阅读更多...
最新文章

Copyright @ 2022~2023