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

单链表专题---暴力算法美学(1)(有视频演示)

1.1 移除链表元素

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

思路一:遍历链表,遇到val就删除,pcur指向val的下一个节点,最后只剩下没有val的链表。

思路二:创建新的链表,头节点用newHead,尾插newTail,pcur来遍历原链表,当pcur!=val,就把数值拿下来,尾插到newTail中,最后新的链表中没有val。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val)//指向头节点的指针,要删除的数值
{//创建一个新链表ListNode* newHead, *newTail;newHead = newTail = NULL;//遍历原链表ListNode* pcur = head;while (pcur)//pcur!=NULL{//找值不为val的节点,尾插到新链表中if (pcur->val != val){//当链表为空时if (newHead == NULL){newHead = newTail = pcur;}else//链表不为空{newTail->next = pcur;//将pcur的值插入newTail的下一个节点newTail = newTail->next;//最后让newTail走向下一个节点}pcur = pcur->next;}}if (newTail)//newTail!=NULLnewTail->next = NULL;return newHead;
}

1.2 反转链表

思路一:创建新的链表,将原链表中的节点拿过来头插。

思路二:创建三个指针,完成链表的翻转。

//反转链表
/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {//判断链表是否为空if(head==NULL)return head;ListNode* n1,*n2,*n3;//创建三个指针实现反转//介绍三个指针分别在什么地方n1 = NULL, n2 = head, n3 = n2->next;while(n2)//判断结束节点,n2!=NULL{n2->next=n1;n1=n2;n2=n3;if(n3)n3=n3->next;}return n1;//n1是链表新的头节点
}

反转链表算法题思路

1.3 链表的中间节点

思路一:遍历原链表,count计节点数,直接返回(count / 2)节点的next节点

思路二:快慢指针

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {//创建两个指针ListNode* fast,* slow;fast=head;slow=head;//两个创建的指针都指向head头节点while(fast && fast->next)//偶数链表遍历结束条件fast=NULL,奇数链表遍历结束条件fast->next=NULL{slow=slow->next;fast=fast->next->next;}return slow;
}

问题:while(fast->next && fast)可以交换位置吗?

不可以!若链表有偶数个节点的情况下,fast最后一次会直接走到空,fast->next会执行报错!

链表的中间节点的思路二:快慢指针

1.3.1拓展提升:删除链表的中间节点

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* deleteMiddle(struct ListNode* head) {struct ListNode* slow, *fast, *dummy, *tmp;dummy=(struct ListNode*)malloc(sizeof( ListNode));dummy->next=head;slow = fast = dummy;while(fast->next != NULL && fast->next->next != NULL) {slow = slow->next;fast = fast->next->next;}tmp = slow->next;slow->next = tmp->next;free(tmp);return dummy->next;
}

问题:为什么要额外申请一个空间放置dummy,dummy->next=head,头节点head本身就是存在的,为什么要有一个dummy来指向head?

答: dummy(虚拟头节点)使用来简化边界情况处理的“工具人”。如果链表只有一个节点,这个唯一节点就是“中间节点”,需要被删除,如果没有dummy,直接删除head,结果会返回NULL,而dummy->next永远指向实际链表的头节点,不管头节点有没有被删除,最后返回的都是dummy->next,不用单独处理头节点被删除导致head无效的情况。

删除链表的中间元素解题思路

http://www.lryc.cn/news/612998.html

相关文章:

  • Numpy科学计算与数据分析:Numpy数组索引与切片入门
  • 【论坛系统自动化功能测试报告】
  • 动手学深度学习(pytorch版):第一节——引言
  • 具身智能机器人 - Reachy Mini
  • MyCAT实战环节
  • 考研复习-计算机组成原理-第三章-存储系统
  • 微服务平台需求-部署一体化文档V1.0
  • cv2.threshold cv2.morphologyEx
  • Ubuntu 25.04 安装 pyenv 并配置多个 python 版本
  • Java并发与数据库锁机制:悲观锁、乐观锁、隐式锁与显式锁
  • 构建一个简洁优雅的 PHP 参数验证器 —— php-schema-validator
  • 金仓KingbaseES逻辑架构,与Oracle/MySQL对比
  • Python实现点云随机一致性(RANSAC)配准——粗配准
  • (Python)Python爬虫入门教程:从零开始学习网页抓取(爬虫教学)(Python教学)
  • 利用vue.js2X写前端搜索页面,express写后端API接口展现搜索数据
  • python数据结构与算法(基础)
  • DrissionPage自动化:高效Web操作新选择
  • 怎么在本地引入字体
  • 深入解析嵌套事务:原理与应用
  • 基于langchain的两个实际应用:[MCP多服务器聊天系统]和[解析PDF文档的RAG问答]
  • HTTP 协议升级(HTTP Upgrade)机制
  • 自动驾驶控制算法——滑模控制(SMC)原理与建模
  • TCP 如何保证可靠性
  • FluentUI-main的详解
  • 多账号管理方案:解析一款免Root的App分身工具
  • B-树与B+树
  • 动力电池点焊机:效率质量双提升,驱动新能源制造升级
  • Dify 从入门到精通(第 20/100 篇):Dify 的自动化测试与 CI/CD
  • Oracle exp imp expdp impdp 命令详解
  • PCB制造中压接孔、插接孔、沉头孔、台阶孔的区别及生产流程