【数据结构与算法】第4课—数据结构单链表OJ练习题

文章目录

  • 1. 移除链表元素
  • 2. 反转链表
  • 3. 找链表中间节点
  • 4. 合并两个有序的链表
  • 5. 分割链表
  • 6. 链表的回文结构
  • 7. 相交链表
  • 8. 判断环形链表
  • 9. 返回环形链表的入环节点
  • 10. 随机链表的复制

1. 移除链表元素

  • 题目

在这里插入图片描述


  • 思路

在这里插入图片描述


在这里插入图片描述


#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//移除链表元素
typedef struct ListNode {int val;struct ListNode* next;
}NodeList;//移除NodeList* removeElements(NodeList* head, int val)
{assert(head);NodeList* newhead = NULL; //新链表的头NodeList* newtail = NULL; //新链表的尾NodeList* pcur = head;//遍历链表while (pcur){if (pcur->val != val){//新链表为空if (newhead == NULL)newhead = newtail = pcur;//新链表不为空else{newtail->next = pcur;newtail = newtail->next;}}pcur = pcur->next;}if (newtail)newtail->next = NULL;return newhead;
}//打印
void NodeListPrint(NodeList* phead)
{assert(phead);while (phead){printf("%d -> ", phead->val);phead = phead->next;}printf("NULL\n");
}void test()
{//初始化NodeList* node1 = (NodeList*)malloc(sizeof(NodeList));NodeList* node2 = (NodeList*)malloc(sizeof(NodeList));NodeList* node3 = (NodeList*)malloc(sizeof(NodeList));NodeList* node4 = (NodeList*)malloc(sizeof(NodeList));NodeList* node5 = (NodeList*)malloc(sizeof(NodeList));NodeList* node6 = (NodeList*)malloc(sizeof(NodeList));NodeList* node7 = (NodeList*)malloc(sizeof(NodeList));if (node1 == NULL || node2 == NULL || node3 == NULL || node4 == NULL || node5 == NULL || node6 == NULL || node7 == NULL){perror("malloc");exit(1);}node1->val = 1;node2->val = 2;node3->val = 6;node4->val = 3;node5->val = 3;node6->val = 5;node7->val = 6;node1->next = node2;node2->next = node3;node3->next = node4;node4->next = node5;node5->next = node6;node6->next = node7;node7->next = NULL;printf("移除之前链表为>:");NodeListPrint(node1);NodeList* newnode = removeElements(node1, 6);printf("移除之后链表为>:");NodeListPrint(newnode);}
int main()
{test();return 0;
}

在这里插入图片描述


2. 反转链表

  • 题目

在这里插入图片描述


  • 思路

在这里插入图片描述


在这里插入图片描述

  • 代码
//反转链表
typedef struct ListNode {int val;struct ListNode* next;
}ListNode;//反转
ListNode* reverseList(ListNode* head)
{if (head == NULL)return head;ListNode* n1, * n2, * n3;n1 = NULL;n2 = head;n3 = n2->next;while (n2){n2->next = n1;n1 = n2;n2 = n3;if (n3)n3 = n3->next;}return n1;
}//打印
void ListNodePrint(ListNode* phead)
{assert(phead);while (phead){printf("%d -> ", phead->val);phead = phead->next;}printf("NULL\n");
}void test()
{//初始化ListNode* node1 = (ListNode*)malloc(sizeof(ListNode));ListNode* node2 = (ListNode*)malloc(sizeof(ListNode));ListNode* node3 = (ListNode*)malloc(sizeof(ListNode));ListNode* node4 = (ListNode*)malloc(sizeof(ListNode));ListNode* node5 = (ListNode*)malloc(sizeof(ListNode));if (node1 == NULL || node2 == NULL || node3 == NULL || node4 == NULL || node5 == NULL){perror("malloc");exit(1);}node1->val = 1;node2->val = 2;node3->val = 3;node4->val = 4;node5->val = 5;node1->next = node2;node2->next = node3;node3->next = node4;node4->next = node5;node5->next = NULL;printf("反转链表之前为>:");ListNodePrint(node1);ListNode* newnode = reverseList(node1);printf("反转链表之后为>:");ListNodePrint(newnode);}
int main()
{test();return 0;
}

3. 找链表中间节点

  • 题目

在这里插入图片描述


在这里插入图片描述


在这里插入图片描述


  • 代码
//练习题:找链表中间节点
typedef struct ListNode 
{int val;struct ListNode* next;
}ListNode;//找中间节点
ListNode* middleNode(ListNode* head)
{ListNode* slow = head;ListNode* fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;
}//打印
void ListNodePrint(ListNode* phead)
{assert(phead);while (phead){printf("%d -> ", phead->val);phead = phead->next;}printf("NULL\n");
}void test()
{//初始化ListNode* node1 = (ListNode*)malloc(sizeof(ListNode));ListNode* node2 = (ListNode*)malloc(sizeof(ListNode));ListNode* node3 = (ListNode*)malloc(sizeof(ListNode));ListNode* node4 = (ListNode*)malloc(sizeof(ListNode));ListNode* node5 = (ListNode*)malloc(sizeof(ListNode));ListNode* node6 = (ListNode*)malloc(sizeof(ListNode));if (node1 == NULL || node2 == NULL || node3 == NULL || node4 == NULL || node5 == NULL || node6 == NULL){perror("malloc");exit(1);}node1->val = 1;node2->val = 2;node3->val = 3;node4->val = 4;node5->val = 5;node6->val = 6;node1->next = node2;node2->next = node3;node3->next = node4;node4->next = node5;node5->next = node6;node6->next = NULL;printf("链表为>:");ListNodePrint(node1);ListNode* newnode = middleNode(node1);printf("链表中间节点为>: %d\n", newnode->val);
}
int main()
{test();return 0;
}

4. 合并两个有序的链表

  • 题目

在这里插入图片描述


  • 思路

在这里插入图片描述


在这里插入图片描述


  • 优化

在这里插入图片描述


在这里插入图片描述


  • 代码
//练习题:合并有序数组
typedef struct ListNode
{int val;struct ListNode* next;
}ListNode;//合并
//ListNode* mergeTwoLists1(ListNode* list1, ListNode* list2) 
//{
//    if (list1 == NULL)
//        return list2;
//    if (list2 == NULL)
//        return list1;
//    ListNode* l1 = list1;
//    ListNode* l2 = list2;
//    ListNode* newHead, * newTail;
//    newHead = newTail = NULL;
//    while (l1 && l2)
//    {
//            if (l1->val < l2->val)
//            {
//                if (newHead == NULL)
//                    newHead = newTail = l1;
//                else
//                {
//                    newTail->next = l1;
//                    newTail = newTail->next;
//                }
//                l1 = l1->next;
//            } 
//            else
//            {
//                if (newHead == NULL)
//                    newHead = newTail = l2;
//                else
//                {
//                    newTail->next = l2;
//                    newTail = newTail->next;
//                }
//                l2 = l2->next;
//            }   
//    }
//    if (l1)
//        newTail->next = l1;
//    if (l2)
//        newTail->next = l2;
//    return newHead;
//}//优化代码
ListNode* mergeTwoLists2(ListNode* list1, ListNode* list2)
{if (list1 == NULL)return list2;if (list2 == NULL)return list1;ListNode* l1 = list1;ListNode* l2 = list2;ListNode* newHead, * newTail;newHead = newTail = (ListNode*)malloc(sizeof(ListNode));//l1 和 l2都不为空while (l1 && l2){if (l1->val < l2->val){newTail->next = l1;newTail = newTail->next;l1 = l1->next;}else{newTail->next = l2;newTail = newTail->next;l2 = l2->next;}}if (l1)newTail->next = l1;if (l2)newTail->next = l2;//保存新链表头节点ListNode* retnode = newHead->next;free(newHead);newHead = NULL;return retnode;
}//打印
void ListNodePrint(ListNode* phead)
{assert(phead);while (phead){printf("%d -> ", phead->val);phead = phead->next;}printf("NULL\n");
}void test()
{//初始化ListNode* node1 = (ListNode*)malloc(sizeof(ListNode));ListNode* node2 = (ListNode*)malloc(sizeof(ListNode));ListNode* node3 = (ListNode*)malloc(sizeof(ListNode));ListNode* node4 = (ListNode*)malloc(sizeof(ListNode));ListNode* node5 = (ListNode*)malloc(sizeof(ListNode));ListNode* node6 = (ListNode*)malloc(sizeof(ListNode));if (node1 == NULL || node2 == NULL || node3 == NULL || node4 == NULL || node5 == NULL || node6 == NULL){perror("malloc");exit(1);}node1->val = 1;node2->val = 2;node3->val = 4;node4->val = 1;node5->val = 3;node6->val = 4;node1->next = node2;node2->next = node3;node3->next = NULL;node4->next = node5;node5->next = node6;node6->next = NULL;printf("合并之前链表1为>:");ListNodePrint(node1);printf("合并之前链表2为>:");ListNodePrint(node4);ListNode* newnode = mergeTwoLists2(node1, node4);printf("合并链表之后>:");ListNodePrint(newnode);
}
int main()
{test();return 0;
}

5. 分割链表

  • 题目

在这里插入图片描述


  • 思路,其中x = 3

在这里插入图片描述


在这里插入图片描述


6. 链表的回文结构

  • 题目:回文结构,左右对称,例如:1221,12121,12321

在这里插入图片描述


  • 思路1:创建新数组,保存链表中所有节点的值,然后再判断数组是否是回文结构即可
//练习题:链表的回文结构
#include <stdbool.h>
typedef struct ListNode
{int val;struct ListNode* next;
}ListNode;
bool chkPalindrome(ListNode* A) 
{int arr[900] = { 0 };int i = 0;ListNode* pcur = A;//遍历链表,将链表的值放入数组while (pcur) {arr[i++] = pcur->val;pcur = pcur->next;}//判断数组是否为回文结构int left = 0;int right = i - 1;//这里i=sizeof(arr)while (left < right) {if (arr[left] != arr[right])return false;left++;right--;}return true;
}
  • 虽然这种方法一定程度帮助我们解题,但该方法受到链表长度的限制,而且严重存在浪费空间

  • 思路2:反转链表中间节点之后的一段链表,然后对比前后两段
#include <stdbool.h>
typedef struct ListNode
{int val;struct ListNode* next;
}ListNode;
//找链表中间节点
ListNode* middleNode(struct ListNode* head) 
{ListNode* slow = head;ListNode* fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;
}
//反转中间节点之后的链表
ListNode* reverseList(ListNode* head) 
{if (head == NULL)return head;ListNode* n1, * n2, * n3;n1 = NULL;n2 = head;n3 = n2->next;while (n2) {n2->next = n1;n1 = n2;n2 = n3;if (n3)n3 = n3->next;}return n1;
}
bool chkPalindrome(ListNode* A) 
{//找中间节点ListNode* mid = middleNode(A);//反转中间节点之后的链表ListNode* right = reverseList(mid);ListNode* left = A;//遍历链表while (right) {if (left->val != right->val) {return false;}left = left->next;right = right->next;}return true;
}

在这里插入图片描述


  • 思路3:逆序链表,然后两个链表对比
//思路3:新建一个链表,作为逆序旧链表的头,然后对比两个链表
#include <stdbool.h>
typedef struct ListNode
{int val;struct ListNode* next;
}ListNode;//逆序链表
ListNode* reverseList(ListNode* head)
{if (head == NULL)return head;ListNode* n1, * n2, * n3;n1 = NULL; n2 = head; n3 = n2->next;while (n2){n2->next = n1;n1 = n2;n2 = n3;if (n3)n3 = n3->next;}return n1;
}
//判断链表是否为回文结构
bool chkPalindrome(ListNode* A) 
{//逆序链表ListNode* newNode = reverseList(A);ListNode* pcur = A;while (pcur){if (pcur->val != newNode->val)return false;pcur = pcur->next;newNode = newNode->next;}return true;
}

7. 相交链表

  • 题目

在这里插入图片描述


  • 思路

在这里插入图片描述


//相交链表
typedef struct ListNode
{int val;struct ListNode* next;
}ListNode;typedef struct ListNode ListNode;
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) 
{ListNode* pa = headA;ListNode* pb = headB;int sizeA = 0, sizeB = 0;      //计数//遍历链表while (pa){pa = pa->next;sizeA++;}while (pb){pb = pb->next;sizeB++;}int gap = abs(sizeA - sizeB);  //链表长度差//定义长短链表,先赋值,再调整ListNode* longList = headA;ListNode* shortList = headB;if (sizeA < sizeB){longList = headB;shortList = headA;}//长链表先走gap步while (gap--){longList = longList->next;}//两个链表对比while (shortList){//相等返回相交节点if (shortList == longList)return shortList;//不等继续向后走shortList = shortList->next;longList = longList->next;}//遍历完链表未找到相交节点return NULL;
}

8. 判断环形链表

  • 题目

在这里插入图片描述


在这里插入图片描述


//判断环形链表
#include <stdbool.h>
typedef struct ListNode ListNode;
typedef struct ListNode
{int val;struct ListNode* next;
}ListNode;bool hasCycle(struct ListNode* head)
{ListNode* slow = head;ListNode* fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;//相遇if (slow == fast)return true;}//走到头未相遇return false;
}
  • 思考:为什么在环形链表中,快指针走两步,慢指针走一步,两个一定会相遇?

在这里插入图片描述


  • 当然fast为3步、4步等都是可以追上的

在这里插入图片描述


9. 返回环形链表的入环节点

  • 题目

在这里插入图片描述


在这里插入图片描述


//返回环形链表入环节点
typedef struct ListNode ListNode;
typedef struct ListNode
{int val;struct ListNode* next;
}ListNode;struct ListNode* detectCycle(struct ListNode* head)
{ListNode* slow = head;ListNode* fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;//相遇if (slow == fast){//定义pcur找入环节点ListNode* pcur = head; while (pcur != slow){pcur = pcur->next;slow = slow->next;}//pcur和slow相遇return pcur;}}//处理空链表return NULL;
}

在这里插入图片描述


  • 证明在带环链表中,相遇点和头节点到入环第一个节点的距离相等

在这里插入图片描述


10. 随机链表的复制

  • 题目

在这里插入图片描述


在这里插入图片描述


  • 思路

在这里插入图片描述


在这里插入图片描述


在这里插入图片描述


在这里插入图片描述


//随机链表的复制
typedef struct Node
{int val;struct Node* next;struct Node* random;
}ListNode;typedef struct Node Node;
//申请节点
Node* BuyNode(int x)
{Node* node = (Node*)malloc(sizeof(Node));if (node == NULL)return -1;node->val = x;node->next = node->random = NULL;return node;
}
//拷贝节点
void AddNode(Node* head)
{Node* pcur = head;while (pcur){Node* next = pcur->next; //保存pcur下一个节点//创建新节点,插入到pcur节点之后Node* newnode = BuyNode(pcur->val);newnode->next = next;pcur->next = newnode;//pcur走向下个节点pcur = next;}
}
//设置random
void Setrandom(Node* head)
{Node* pcur = head;while (pcur){Node* copy = pcur->next;if (pcur->random)copy->random = pcur->random->next;pcur = copy->next;}
}
struct Node* copyRandomList(struct Node* head)
{if (head == NULL){return head;}//1.拷贝节点AddNode(head);//2.安置randomSetrandom(head);//3.断开链表Node* newHead, * newTail;Node* pcur = head;newHead = newTail = pcur->next;while (newTail->next){pcur = newTail->next;newTail->next = pcur->next;newTail = newTail->next;}return newHead;
}

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

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

相关文章

【功能安全】技术安全概念TSC

目录 01 TSC定义 02 TSC注意事项 03 TSC案例 01 TSC定义 所处位置 TSC:Technical safety concept技术安全概念 TSR:Technical safety requirement技术安全需求 在系统开发阶段属于安全活动4-6 系统层产品开发示例 TSC目的

传输层UDP

再谈端口号 端口号&#xff1a;标识了主机上进行通信的不同的应用程序 在TCP/IP 协议中我们用“源IP”"源端口号" “目的IP”“目的端口号” “协议号”五元组来标识一个通信 用netstat -n 查看 查看网络信息&#xff0c;我们有两种命令查看网络通信1.用netsta…

力扣刷题(sql)--零散知识点(1)

通过一段时间的刷题&#xff0c;感觉自己的sql能力逐渐上去&#xff0c;所以不会像前三道题一样讲那么详细了&#xff0c;这里主要会讲到一些特殊的知识点和方法。另外&#xff0c;我的建议是做完一个题有好的想法赶紧记录下来&#xff0c;不要想着最后汇总&#xff0c;不然会懒…

通过cv库智能切片 把不同的分镜切出来 自媒体抖音快手混剪

用 手机自动化脚本&#xff0c;从自媒体上获取视频&#xff0c;一个商品对应几百个视频&#xff0c;我们把这几百个视频下载下来&#xff0c;进行分镜 视频切片&#xff0c;从自媒体上下载视频&#xff0c;通过cv库用直方图识别每个镜头进行切片。 下载多个图片进行视频的伪原…

香橙派5(RK3588)使用npu加速yolov5推理的部署过程

香橙派5使用npu加速yolov5推理的部署过程 硬件环境 部署过程 模型训练(x86主机) 在带nvidia显卡(最好)的主机上进行yolo的配置与训练, 获取最终的best.pt模型文件, 详见另一篇文档 模型转换(x86主机) 下载airockchip提供的yolov5(从pt到onnx) 一定要下这个版本的yolov5, …

sass软件登录设定——未来之窗行业应用跨平台架构

一、saas软件开发中登录设计 以为大公司为参考思迅在登录时候需要录入商户号 二、独立商户商户好处 1.每个店铺的账户是独立的&#xff0c;保护商户职员账户信息的相对安全。 2.不同店铺可以试用相同用户名

LDR6020:为VR串流线方案注入高效能与稳定性

随着虚拟现实&#xff08;VR&#xff09;技术的不断发展&#xff0c;VR设备已经成为连接用户与沉浸式体验的重要桥梁。而VR串流线&#xff0c;作为这一技术的重要组成部分&#xff0c;更是承担着传输高质量图像、音频及数据的重任。在这个过程中&#xff0c;一款功能强大、性能…

【计网】从零开始认识IP协议 --- 认识网络层,认识IP报头结构

从零开始认识IP协议 1 网络层协议1.1 初步认识IP协议1.2 初步理解IP地址 2 IP协议报头3 初步理解网段划分 1 网络层协议 1.1 初步认识IP协议 我们已经熟悉了传输层中的UDP和TCP协议&#xff0c;接下来我们来接触网络层的协议&#xff1a; 网络层在计算机网络中的意义主要体现…

寻找大自然的颜色

走在停停&#xff0c;停停走走&#xff0c;恍惚间一天过去了&#xff0c;转瞬间一年过去了&#xff0c;身边的一切在变化又不在变化&#xff0c;生活是自己的又不是自己的。 今天是个特殊的日子&#xff0c;其实前几天对我而言就算特殊的日子了&#xff0c;一个心里暗暗等待着却…

Maven项目管理工具-初始+环境配置

1. Maven的概念 1.1. 什么是Maven Maven是跨平台的项目管理工具。主要服务于基于Java平台的项目构建&#xff0c;依赖管理和项目信息管理。 理想的项目构建&#xff1a;高度自动化&#xff0c;跨平台&#xff0c;可重用的组件&#xff0c;标准化的流程 maven能够自动下载依…

python项目实战——多线程爬虫

多线程爬虫 文章目录 多线程爬虫概念并行并发Python多线程用途threading模块小知识----函数体内pass的用处1. **占位符**2. **控制结构**3. **定义接口**总结 代码解读单线程--串行多线程--并行查看当前程序的线程让主函数等待子线程结束&#xff0c;再运行---.join()join()方法…

C# 串口通信教程

串口通信&#xff08;Serial Communication&#xff09;是一种用于设备之间数据传输的常见方法&#xff0c;通常用于与外部硬件设备&#xff08;如传感器、机器人、微控制器&#xff09;进行通信。在 C# 中&#xff0c;System.IO.Ports 命名空间提供了与串口设备交互的功能&…

【Linux | 网络I/O模型】五种网络I/O模型详解

1、数据传输过程 在 Linux 系统中&#xff0c;数据传输是通过 I/O 操作来实现的。I/O 操作是指数据从应用程序到内核&#xff0c;再到硬件设备&#xff08;如磁盘、网络接口&#xff09;的过程。 操作系统为了保护自己&#xff0c;设计了用户态、内核态两个状态。应用程序一般工…

数据库的诗篇:深入探索 MySQL 表操作的艺术与哲学

文章目录 前言&#x1f338;一、创建表——搭建数据存储的基础框架1.1 基本语法1.2 创建表的实际案例解释&#xff1a; 1.3 表设计的最佳实践 &#x1f338;二、查看表结构——快速了解数据库设计2.1 使用 DESC 命令解释&#xff1a; 2.2 使用 SHOW COLUMNS 命令2.3 使用 SHOW …

Java线程安全

目录 一.引入 二.介绍 1.概念 2.产生的原因 三.修改操作不是原子性 1.分析问题 2.解决问题&#xff08;锁&#xff09; 四.可重入与不可重入 五.死锁 1.引入 2.死锁的三种情况 3.构成死锁的必要条件 六.内存可见性 1.引入 2.产生原因 3.解决问题 七.指令重排序…

让你的 IDEA 使用更流畅 | IDEA内存修改

随着idea使用越来越频繁&#xff0c;笔者最近发现使用过程中有时候会出现卡顿现象&#xff0c;例如&#xff0c;启动软件变慢&#xff0c;打开项目的速度变慢等&#xff1a; 因此如果各位朋友觉得最近也遇到了同样的困惑&#xff0c;不妨跟着笔者一起来设置IDEA的内存大小吧~ …

虚拟现实在制造业中的应用

当你想到制造业中的虚拟现实技术时&#xff0c;你脑海中闪过的第一个念头是什么&#xff1f;从目前来看&#xff0c;只需几年时间&#xff0c;制造业就将离不开虚拟现实技术的帮助。实施虚拟现实应用对制造业来说都有诸多好处。通常情况下&#xff0c;制造设施都是由各种机器组…

基于neo4j的学术论文关系管理系统

正在为毕业设计头疼&#xff1f;又或者在学术研究中总是找不到像样的工具来管理浩瀚的文献资料&#xff1f;今天给大家介绍一款超实用的工具——基于Neo4j的学术论文关系管理系统&#xff0c;让你轻松搞定学术文献的管理与展示&#xff01;&#x1f389; 系统的核心是什么呢&a…

一个基于.NET8+WPF开源的简单的工作流系统

项目介绍 AIStudio.Wpf.AClient 是一个基于 WPF (Windows Presentation Foundation) 构建的客户端框架&#xff0c;专为开发企业级应用而设计。该项目目前版本为 6.0&#xff0c;进行了全面优化和升级&#xff0c;提供了丰富的功能和模块&#xff0c;以满足不同场景下的开发需…

清华大学《2022年+2021年822自动控制原理真题》 (完整版)

本文内容&#xff0c;全部选自自动化考研联盟的&#xff1a;《清华大学822自控考研资料》的真题篇。后续会持续更新更多学校&#xff0c;更多年份的真题&#xff0c;记得关注哦~ 目录 2022年真题 2021年真题 Part1&#xff1a;2022年2021年完整版真题 2022年真题 2021年真题…