C/C++数据结构之链表题目答案与解析
时间：2024-04-09 16:40:25 来源：网络cs 作者：康由 栏目：卖家故事 阅读：
个人主页：点我进入主页
专栏分类：C语言初阶 C语言程序设计————KTV C语言小游戏 C语言进阶
C语言刷题 数据结构初阶
欢迎大家点赞，评论，收藏。
一起努力，一起奔赴大厂。
目录
1.前言
2.题目解析
2.1 移除链表元素
2.2反转链表
2.3链表的中间结点
2.4链表中倒数第k个结点
2.5合并两个有序链表
2.6链表分割
3.结语
1.前言
在前面我们讲解了一些关于链表的内容，其中还有一些关于链表的习题，今天我们主要对这些题目进行解析。
2.题目解析
2.1 移除链表元素
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6输出：[1,2,3,4,5]
示例 2：
输入：head = [], val = 1输出：[]
示例 3：
输入：head = [7,7,7,7], val = 7输出：[]
提示：
列表中的节点数目在范围[0, 104] 内1 <= Node.val <= 500 <= val <= 50 struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode *phead=(struct ListNode*)malloc(sizeof(struct ListNode)); phead->next=head; struct ListNode *p=phead; struct ListNode *q=phead->next; if(!q) return NULL; while(q) { if(q->val==val) { p->next=q->next; free(q); q=p->next; } else { p=p->next; q=q->next; } } return phead->next;}在这里我们需要对链表看是不是空的，只有一个节点，有多个节点这些情况进行讨论，我们建立一个带头节点的节点，然后将这些连上，先判断是不是空，不是空两个指针，一个指向建立的头节点，另一个指向后一个节点，我们针对后面的节点进行判断，值相等进行去除 操作，最后返回头节点的下一个节点。
2.2反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]输出：[2,1]
示例 3：
输入：head = []输出：[]
提示：
链表中节点的数目范围是[0, 5000]-5000 <= Node.val <= 5000
struct ListNode* reverseList(struct ListNode* head) { struct ListNode *phead=(struct ListNode *)malloc(sizeof(struct ListNode)); struct ListNode *p=head; phead->next=NULL; if(!p) return NULL; struct ListNode *q=p->next; while(p) { p->next=phead->next; phead->next=p; p=q; if(q) q=q->next; } return phead->next;}我们建立一个头节点，然后连起来，判断是不是为空，我们知道头插相当于将数据进行反转，所以我们可以将链表一次一次地拆下来，然后头插到头节点上，我们用两个指针，一个用来记录位置，一个用来进行拆地操作。
2.3链表的中间结点
给你单链表的头结点 head ，请你找出并返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：head = [1,2,3,4,5]输出：[3,4,5]解释：链表只有一个中间结点，值为 3 。
示例 2：
输入：head = [1,2,3,4,5,6]输出：[4,5,6]解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。
提示：
链表的结点数范围是[1, 100]1 <= Node.val <= 100 struct ListNode* middleNode(struct ListNode* head) { struct ListNode*fast=head,*slow=head; if(!fast) return NULL; while(fast&&fast->next) { fast=(fast->next)->next; slow=slow->next; } return slow;}我们先对链表进行判断是不是空链表，然后利用快慢指针进行操作，快指针每次走两步，满指针每次走一步，当快指针为空且快指针地下一个指针不为空就进行，知道出现这两个有一个为空才停止。
2.4链表中倒数第k个结点
输入一个链表，输出该链表中倒数第k个结点。
示例1
输入：
1,{1,2,3,4,5} 复制返回值：
{5} struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { // write code here struct ListNode * flast=pListHead; while(k--) { if(flast==NULL) return NULL; flast=flast->next; } struct ListNode *slow=pListHead; while(flast) { slow=slow->next; flast=flast->next; } return slow;}在这里我们同样用快慢指针，我们先让快指针走k步如果在k次中出现为空说明超出限制，返回空，快指针走k步后快慢指针一起走当快指针指向空此时地慢指针就是倒数第k个节点。
2.5合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []输出：[]
示例 3：
输入：l1 = [], l2 = [0]输出：[0]
提示：
两个链表的节点数目范围是[0, 50]-100 <= Node.val <= 100l1 和 l2 均按 非递减顺序 排列 struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { struct ListNode*phead=(struct ListNode *)malloc(sizeof(struct ListNode)); struct ListNode*s1=list1,*s2=list2,*cur=phead; while(s1&&s2) { if(s1->val<=s2->val) { cur->next=s1; cur=cur->next; s1=s1->next; cur->next=NULL; } else { cur->next=s2; cur=cur->next; s2=s2->next; cur->next=NULL; } } if(!s1) { cur->next=s2; } else{ cur->next=s1; } return phead->next;}在这里我们创建一个头节点，然后两个指针指向这两个链表，当这两个指针有一个为空时结束循环，循环里就是找到这两个指针地数据哪一个小，去连上头节点进行尾插，这两有一个为空时另外一个直接连上。
2.6链表分割
现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
class Partition {public: ListNode* partition(ListNode* pHead, int x) { // write code here ListNode *list1=(ListNode*)malloc(sizeof(ListNode)); ListNode *list2=(ListNode*)malloc(sizeof(ListNode)); ListNode*s1=list1,*s2=list2; list1->next=NULL; list2->next=NULL; ListNode*p=pHead; while(p) { if(p->val<x) { s1->next=p; p=p->next; s1->next=NULL; } else { s2->next=p; p=p->next; s2->next=NULL; } } s1->next=list2->next; free(list2); return list1->next;}我们创建两个头节点，然后将小于x的放在一个链表上，大于等于X的放在另一个链表，最后连起来。
3.结语
数据结构的学习非常的重要，我们想要学习好数据结构需要我们多多的刷题，希望大家可以在平时多多刷题来提升自己，最后希望大家可以三连一下
阅读本书更多章节>>>>本文链接：https://www.kjpai.cn/gushi/2024-04-09/156113.html，文章来源：网络cs，作者：康由，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！