东莞免费网站建站模板,长沙网站大全,cms监控软件下载官网,网站空间不够用怎么办欢迎来到我的#xff1a;世界
该文章收入栏目#xff1a;链表
希望作者的文章对你有所帮助#xff0c;有不足的地方还请指正#xff0c;大家一起学习交流 ! 目录 前言第一题#xff1a;反转一个链表第二题#xff1a;链表内指定区间反转第三题#xff1a;判断一个链表…
欢迎来到我的世界
该文章收入栏目链表
希望作者的文章对你有所帮助有不足的地方还请指正大家一起学习交流 ! 目录 前言第一题反转一个链表第二题链表内指定区间反转第三题判断一个链表是否为回文结构 总结 前言 对于我来说这个博客是一个学习的地方就像我的上篇文章一样有老铁们的支持陪伴我很满足这个栏目我会继续坚持下去108回就像我的108难一样只要撑过磨难一定能取到真经
--------------------------对过程全力以赴对结果淡然处之 第一题反转一个链表 地址oj地址 解题思路 思路让链表翻转过来可以先创造一个新的链表头指针指向空然后原来的链表一个一个头插到新的指针到时候在返回新创造的链表起始位置。按照这个思路 我们需要创造一个新指针变量指向空 然后接下来就是将原链表头插入newnode 这里需要注意一下如果按照头插入newnode,如果指针pHead将结点插入来的话那pHead原指向的下一个结点就丢失了所以这里需要创造一个新的指针 next 存放pHead所指的下一个结点这样才能找回去 后面步骤依次将后续头插入这里有一步也需要注意记得让cur找回到next的结点然后使next再指向cur下一个结点 直到pHead为空结束最后返回newnode 代码
struct ListNode* ReverseList(struct ListNode* head ) {// write code herestruct ListNode* newnode NULL;struct ListNode* cur head;//头插while (cur) {//为了cur能够找回下一个结点struct ListNode* next cur-next;//头插cur-next newnode;newnode cur;//cur指针找回到下一个结点cur next;}return newnode;
}第二题链表内指定区间反转 地址oj地址 加强版的反转链表 思路 先利用cur指针指向该链表 head 的位置依次往下找,直到遇到要反转区间的起始位置ret指针记录住该位置 (后面链接起来的要用到);在让cur往下走这里应该注意要用prve指针判断在原来链表是否有结点是否有节点关系到后面链接时的方式是head还是prve-next这点很重要然后从cur现在位置开始进行头插为了反转给区间链表到一个新链表newnode直到走到区间的末尾都头插入后(包括了末尾这个结点);之后就是链接的步骤需要将head和newnode链接起来所以这里用到了prve进行判断 具体的更详细在下面细讲 在这里我想着重想解释一下为什么要设置prve 这里来举两个测试用例 第一个这种相当于第二种情况 创造cur指针指向的是headprve先是指向空开始找区间起始位置根据m值(m为2则应该找第二个结点)每找过一个节点将cur给到prve(这是为了判断区别出是不是从头就开始头插在后面链接时会用来判断其链接的方式在上面有详细解释)直到找到区间起始(如果m1则直接从第一个进行头插这个时候的prve仍指向空)在这个位置设置ret下面进行依次头插入 直到区间所有头插完 最后进行链接起来让prve-next 指向newnode ret-next指向cur最后返回head 还有一个测试用例 这就相当于的是情况1 全部进行了反转 全部头插完后将head指向newnode 代码实现
#include math.h
struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {// write code hereif (head NULL || head-next NULL || m n)return head;struct ListNode* cur head;struct ListNode* newnode NULL, * tail NULL;newnode (struct ListNode*)malloc(sizeof(struct ListNode));newnode-next tail NULL;//找到m的最后一个int countm;struct ListNode*prevNULL;while(count--1){prevcur;curcur-next;}struct ListNode*retcur;//进行头插反转int lenn-m1;while(len--){struct ListNode*nextcur-next;cur-nextnewnode-next;newnode-nextcur;curnext;}//链接if(prevNULL){headnewnode-next;ret-nextcur;}else {prev-nextnewnode-next;ret-nextcur;}
return head;
}第三题判断一个链表是否为回文结构 地址oj地址 首先我们要知道什么是回文结构如 偶数回文1 2 2 1 奇数回文1 2 3 2 1 解题思路 思路找到中间的结点然后让中间结点后的所有节点反转然后返回的这个中间节点 rever 与该链表的第一个结点进行依次比较值相等就完后走直到指向中间的这个节点 rever 指向空 这里会用到返回中间结点的这个函数和反转一串链表函数(就是本篇文章的第一题)这两个我们之前已经写过了老铁们可以去看看返回中间结点; 代码
struct ListNode* middleNode(struct ListNode* head) {// write code here//返回中间结点的地址//设置快慢指针struct ListNode* sur head, * dst head;//当dst指针为空或dst指向的next为空就停下while (dst dst-next) {sur sur-next;dst dst-next-next;}return sur;}//反转一串链表并返回该链表的头地址struct ListNode* ReverseList(struct ListNode* head ) {// write code herestruct ListNode* newnodeNULL;struct ListNode* cur head;while (cur) {struct ListNode* next cur-next;//头插cur-next newnode;newnode cur;cur next;}return newnode;}//实现判断是否为回文结构
bool isPail(struct ListNode* head ) {// write code herestruct ListNode* mid middleNode(head);struct ListNode* rever ReverseList(mid);while (rever) {if (head-val ! rever-val) {return false;}rever rever-next;head head-next;}return true;
}总结 对每到题可能还是可以优化的如果还有更好的方法的老铁可以在评论区里面一起进行讨论哦在后面随着小孩的知识储备越多小孩肯定还会加以优化优化 到了最后感谢支持
我还想告诉你的是 ------------对过程全力以赴对结果淡然处之 也是对我自己讲的
