当前位置: 首页 > news >正文

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;//返回新的头结点}            
};

  

参考如下:

代码随想录

相关文章:

  • 串口环保212设备 转 profinet IO协议项目案例
  • Diffusion Model, Stable Diffusion, Stable Diffusion XL 详解
  • 前后端分离跨域问题解决方案
  • MagicPose4D:解锁AI驱动的3D模型动作新纪元
  • [C#]winform部署官方yolov10目标检测的onnx模型
  • 【Qt秘籍】[003]-Qt环境变量配置-磨刀不误砍柴工
  • [FlareOn6]Overlong
  • 知识分享:大数据信用花导致的评分不足多久能恢复
  • 领域驱动设计(DDD)学习笔记之:基础理论与概念
  • return _VF.meshgrid(tensors, **kwargs) 的参考解决方法
  • B2124 判断字符串是否为回文
  • 动态规划之买卖股票大集合
  • ②单细胞学习-组间及样本细胞比例分析
  • 深度剖析:为什么 Spring 和 IDEA 都不推荐使用 @Autowired 注解
  • k8s问题
  • [分享]iOS开发-关于在xcode中引用文件夹右边出现问号的解决办法
  • 2018一半小结一波
  • Git 使用集
  • Gradle 5.0 正式版发布
  • Js基础知识(一) - 变量
  • LeetCode29.两数相除 JavaScript
  • Python学习笔记 字符串拼接
  • Sass Day-01
  • UEditor初始化失败(实例已存在,但视图未渲染出来,单页化)
  • 表单中readonly的input等标签,禁止光标进入(focus)的几种方式
  • 关于字符编码你应该知道的事情
  • 基于Mobx的多页面小程序的全局共享状态管理实践
  • ------- 计算机网络基础
  • 检测对象或数组
  • 精益 React 学习指南 (Lean React)- 1.5 React 与 DOM
  • 前端之Sass/Scss实战笔记
  • 驱动程序原理
  • 使用权重正则化较少模型过拟合
  • 我感觉这是史上最牛的防sql注入方法类
  • # Pytorch 中可以直接调用的Loss Functions总结:
  • #、%和$符号在OGNL表达式中经常出现
  • #pragma multi_compile #pragma shader_feature
  • #我与Java虚拟机的故事#连载05:Java虚拟机的修炼之道
  • (2.2w字)前端单元测试之Jest详解篇
  • (day18) leetcode 204.计数质数
  • (delphi11最新学习资料) Object Pascal 学习笔记---第13章第1节 (全局数据、栈和堆)
  • (ISPRS,2023)深度语义-视觉对齐用于zero-shot遥感图像场景分类
  • (Matalb时序预测)PSO-BP粒子群算法优化BP神经网络的多维时序回归预测
  • (补)B+树一些思想
  • (补充):java各种进制、原码、反码、补码和文本、图像、音频在计算机中的存储方式
  • (附源码)springboot“微印象”在线打印预约系统 毕业设计 061642
  • (十六)一篇文章学会Java的常用API
  • (五)网络优化与超参数选择--九五小庞
  • (一)硬件制作--从零开始自制linux掌上电脑(F1C200S) <嵌入式项目>
  • (转)C语言家族扩展收藏 (转)C语言家族扩展
  • .gitignore文件忽略的内容不生效问题解决
  • .NetCore实践篇:分布式监控Zipkin持久化之殇
  • @AliasFor注解
  • @hook扩展分析
  • @test注解_Spring 自定义注解你了解过吗?