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) { // 注意这里不是ifListNode* 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->nextcur->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;//返回新的头结点}            
};

  

参考如下：

代码随想录

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

啊哈!算法-第2章-栈、队列、链表

啊哈!算法-第2章-栈、队列、链表

啊哈!算法-第2章-栈、队列、链表 第1节 解密qq号——队列第2节 解密回文——栈第3节 纸牌游戏——小猫钓鱼第4节 链表第5节 模拟链表 第1节 解密qq号——队列 新学期开始了&#xff0c;小哈是小哼的新同桌(小哈是个大帅哥哦~)&#xff0c;小哼向小哈询问 QQ 号&#xff0c; 小…
阅读更多...
有限元之抛物型方程初边值问题解法

有限元之抛物型方程初边值问题解法

目录 一、原方程的变分形式 二、有限元法进行空间半离散 三、差分法进行时间全离散 四、相关量的数值计算 五、编程时的说明 六、算例实现 6.1 C代码 6.2 计算结果 本节我们将采用有限元法联合差分法来数值求解抛物型方程的初边值问题&#xff1a; 其中常数。 一、原方…
阅读更多...
Element-UI 入门指南：从安装到自定义主题的详细教程

Element-UI 入门指南：从安装到自定义主题的详细教程

Element-UI 是一个基于 Vue.js 的前端组件库&#xff0c;它提供了丰富的 UI 组件&#xff0c;可以帮助开发者快速构建高质量的用户界面。以下是使用 Element-UI 的快速入门指南&#xff1a; 安装 Element-UI Element-UI 是一个基于 Vue.js 的组件库&#xff0c;它提供了丰富的…
阅读更多...
LangChain入门开发教程（一）：Model I/O

LangChain入门开发教程（一）：Model I/O

官方文档&#xff1a;https://python.langchain.com/docs/get_started/introduction/ LangChain是一个能够利用大语言模型&#xff08;LLM&#xff0c;Large Language Model&#xff09;能力进行快速应用开发的框架&#xff1a; 高度抽象的组件&#xff0c;可以像搭积木一样&a…
阅读更多...
LeetCode2336无限集中的最小数字

LeetCode2336无限集中的最小数字

题目描述 现有一个包含所有正整数的集合 [1, 2, 3, 4, 5, …] 。实现 SmallestInfiniteSet 类&#xff1a;SmallestInfiniteSet() 初始化 SmallestInfiniteSet 对象以包含 所有 正整数。int popSmallest() 移除 并返回该无限集中的最小整数。void addBack(int num) 如果正整数 …
阅读更多...
基于Python实现 HR 分析（逻辑回归和基于树的机器学习）【500010104】

基于Python实现 HR 分析（逻辑回归和基于树的机器学习）【500010104】

介绍 数据集说明 此数据集包含与员工有关的综合属性集合&#xff0c;从人口统计细节到与工作相关的因素。该分析的主要目的是预测员工流动率并辨别导致员工流失的潜在因素。 在这个数据集中&#xff0c;有14,999行&#xff0c;10列&#xff0c;以及这些变量&#xff1a;满意度…
阅读更多...
Python轻量级的插件框架库之pluginbase使用详解

Python轻量级的插件框架库之pluginbase使用详解

概要 在软件开发中，插件系统是一个常见的需求。插件系统允许开发者动态加载和卸载功能模块，从而提高应用程序的灵活性和可扩展性。Python的pluginbase库是一个轻量级的插件框架，旨在简化插件系统的构建过程。pluginbase库提供了一套简单易用的API，使开发者能够快速集成插件…
阅读更多...
leetCode-hot100-数组专题之子数组+二维数组

leetCode-hot100-数组专题之子数组+二维数组

数组专题之子数组二维数组 子数组238.除自身以外数组的乘积560.和为K的子数组 二维数组48.旋转图像 子数组 数组的子数组问题是算法中常见的一类问题&#xff0c;通常涉及到数组的连续元素。在解决这类问题时&#xff0c;常用的方法有前缀和、滑动窗口、双指针&#xff0c;分治…
阅读更多...
Sping源码（九）—— Bean的初始化（非懒加载）— getMergedLocalBeanDefinition

Sping源码（九）—— Bean的初始化（非懒加载）— getMergedLocalBeanDefinition

序言 前两篇文章介绍了Bean初始化之前的一些准备工作&#xff0c;包括设置BeanFacroty的ConversionService属性以及将Bean进行冻结。这篇文章将会进入到preInstantiateSingletons方法。进一步了解Bean的初始化流程。 preInstantiateSingletons public void preInstantiateSin…
阅读更多...
一篇文章讲透排序算法之快速排序

一篇文章讲透排序算法之快速排序

前言 本篇博客难度较高&#xff0c;建议在学习过程中先阅读一遍思路、浏览一遍动图&#xff0c;之后研究代码&#xff0c;之后仔细体会思路、体会动图。之后再自己进行实现。 一.快排介绍与思想 快速排序相当于一个对冒泡排序的优化&#xff0c;其大体思路是先在文中选取一个…
阅读更多...
装机必备——截图工具Snipaste安装教程

装机必备——截图工具Snipaste安装教程

装机必备——截图工具Snipaste安装教程 软件下载 软件名称&#xff1a;Snipaste2.7 软件语言&#xff1a;简体中文 软件大小&#xff1a;15.37M 系统要求&#xff1a;Windows7或更高&#xff0c; 32/64位操作系统 硬件要求&#xff1a;CPU2GHz &#xff0c;RAM2G或更高 下载通…
阅读更多...
数据结构（七）查找

数据结构（七）查找

2024年5月26日一稿&#xff08;王道P291&#xff09; 7.1 查找的基本概念 7.2 顺序查找和折半查找 7.2.1 顺序查找 7.2.2 折半查找 7.2.3 分块查找 7.3 树形查找 7.3.1 二叉排序树(BST) 7.3.2 平衡二叉树 7.4 B树和B树 7.4.1 B树及其基本操作 7.4.2 B树的基本概念 7.5 散列&…
阅读更多...
idea、datagrip注册记录下

idea、datagrip注册记录下

一、DataGrip注册 DataGrip版本号&#xff1a;DataGrip 2023.2 访问地址&#xff1a;https://3.jetbra.in/ 点击“hardbin.com”&#xff0c;下载“jetbra.zip” 在vm里面添加上&#xff1a; -javaagent:D:\work\idea\jetbra\ja-netfilter.jarjetbrains重启datagrip 在刚刚…
阅读更多...
【408真题】2009-28

【408真题】2009-28

“接”是针对题目进行必要的分析&#xff0c;比较简略&#xff1b; “化”是对题目中所涉及到的知识点进行详细解释&#xff1b; “发”是对此题型的解题套路总结&#xff0c;并结合历年真题或者典型例题进行运用。 涉及到的知识全部来源于王道各科教材&#xff08;2025版&…
阅读更多...
WebGL技术在教育培训中的应用

WebGL技术在教育培训中的应用

WebGL技术在教育培训中的应用非常广泛&#xff0c;通过其强大的三维图形处理能力&#xff0c;能够为教育培训提供更加生动、互动和沉浸式的学习体验。以下是WebGL在教育培训中的几个主要应用及其具体实现。北京木奇移动技术有限公司&#xff0c;专业的软件外包开发公司&#xf…
阅读更多...
奶奶也能看懂的耦合协调度分析

奶奶也能看懂的耦合协调度分析

不会计算&#xff1f;跟着文献学起来~ 案例数据连接&#xff08;复制链接后粘贴到浏览器中&#xff09;&#xff1a; 耦合协调度数据​spssau.com/spssaudata.html?shareDataF363000CD033FF15E557BB75B9B0D412 假如你有这样一组数据&#xff1a; 如何进行计算分析耦合协调度…
阅读更多...
蓝桥楼赛第30期-Python-第三天赛题 统计学习数据题解

蓝桥楼赛第30期-Python-第三天赛题 统计学习数据题解

楼赛 第30期 Python 模块大比拼 统计学习数据 介绍 JSON&#xff08;JavaScript Object Notation, /ˈdʒeɪsən/&#xff09;是一种轻量级的数据交换格式&#xff0c;最初是作为 JavaScript 的子集被发明的&#xff0c;但目前已独立于编程语言之外&#xff0c;成为了通用的…
阅读更多...
淘宝API探秘：一键获取店铺所有商品的魔法之旅

淘宝API探秘：一键获取店铺所有商品的魔法之旅

在数字时代的今天&#xff0c;数据已经成为了商业世界中的魔法石。而对于淘宝店主或者那些想要深入探索淘宝数据的人来说&#xff0c;淘宝API就像是打开阿里巴巴宝藏库的钥匙。今天&#xff0c;我们就来一起探索如何使用淘宝API&#xff0c;特别是如何获取店铺所有商品的接口&a…
阅读更多...
ElasticSearch学习篇12_《检索技术核心20讲》基础篇

ElasticSearch学习篇12_《检索技术核心20讲》基础篇

背景 学习极客实践课程《检索技术核心20讲》https://time.geekbang.org/column/article/215243 课程分为基础篇、进阶篇、系统案例篇 主要记录企业课程学习过程课程大纲关键点&#xff0c;以文档形式记录笔记。 内容 检索技术&#xff1a;它是更底层的通用技术&#xff0c…
阅读更多...
芝加哥大学最新研究：GPT-4与财务预测，重塑财务分析的未来

芝加哥大学最新研究：GPT-4与财务预测，重塑财务分析的未来

最近&#xff0c;芝加哥大学的研究团队发表了一篇突破性的研究&#xff0c;展示了大型语言模型&#xff08;LLM&#xff09;&#xff0c;特别是 OpenAI 开发的 GPT-4&#xff0c;如何在财务报表分析领域取得了与专业分析师相匹配甚至超越的表现。这项研究不仅凸显了人工智能在高…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023