c语言|链表刷题笔记(较难篇) (c实现)(跑路人笔记) 编程语言|经验分享|开发语言

文章目录

前言
翻转单链表--力扣简单
- 正确代码
- 思路
链表的中间节点--力扣简单
- 正确代码
- 讲解
链表的回文结构(牛客较难)?♂?
- 正确代码
- 讲解
结尾

前言本篇包含牛客两道较难题和部分简单题,前面的简单题有为后面的难题做铺垫
前两道题是为第三道较难题做铺垫
对了前面两道题我之前有篇博客写了所以我直接沾过来了=-=.
然后好像被检测啥的了我弄成自己可见了=-=大家见谅.
要是感觉有不懂的可以私聊或评论我,我马上改
翻转单链表–力扣简单正确代码

/** * Definition for singly-linked list. * struct ListNode { *int val; *struct ListNode *next; * }; */ struct ListNode* reverseList(struct ListNode* head) { struct ListNode* cur = head; struct ListNode* prev = NULL; while(cur!=NULL) { struct ListNode* next = cur->next; cur->next = prev; prev = cur; cur = next; } return prev; }

思路我的思路是将链表的指针进行翻转
比如:

文章图片

要翻转这个链表
我们就要知道链表的上一位,下一位
然后让当前的链表内容的next指向上一位,然后通过next变量向下移动链表当当前内容为NULL时停止循环.
所以这道题只需要三个变量就可以解决问题=-=.
链表的中间节点–力扣简单连接
给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
正确代码

/** * Definition for singly-linked list. * struct ListNode { *int val; *struct ListNode *next; * }; */struct ListNode* middleNode(struct ListNode* head) { assert(head); struct ListNode* slow = head; struct ListNode* fast = head; while(fast!=NULL&&fast->next!=NULL) { slow = slow->next; fast = fast->next->next; } return slow; }

讲解使用快慢指针,慢指针向后走一步的时候快指针走两步就好了=-=.
思路很简单但是其实还挺难想的=-=.
链表的回文结构(牛客较难)?♂? 连接

文章图片

回文结构:

指逆置后和正序一致的数据如1221逆置后还是1221所以1221为true
再如123 逆置后为321 就不为回文结构.

不得不说一句,牛客的题目描述和报错实在是做的一般般?♂?.
今天不小心调用了空指针他直接给我个段报错实在是难受?♂?.
【c语言|链表刷题笔记(较难篇) (c实现)(跑路人笔记)】不小心发了点牢骚=-=.我们继续
正确代码提醒一下虽然这是C++形势的代码但是内部都是C写的所以大家不用被劝退

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; */ class PalindromeList { public: bool chkPalindrome(ListNode* A) { ListNode*fast=A ,*slow=A,*cur=NULL,*next=NULL,*prev=NULL; while(fast&&fast->next) { fast = fast->next->next; slow = slow->next; } next = slow->next; prev = NULL; cur = slow; while(cur) { cur->next = prev; prev = cur; cur = next; next = next->next; } ListNode* newhead1 = A; ListNode* newhead2 = prev; while(newhead2) { if(newhead1->val ==newhead2->val) { newhead1 = newhead1->next; newhead2 = newhead2->next; } else { return false; } } return true; } };

讲解我们这道题的思路是先通过快慢指针找到链表的中间节点,然后通过三个指针进行中间节点后的逆置,最后再通过遍历进行比较
整体思路的时间复杂度为O(N)空间复杂度为O(1)符合题目要求

while(fast&&fast->next) { fast = fast->next->next; slow = slow->next; }

寻找中间节点通过快慢指针.

next = slow->next; prev = NULL; cur = slow; while(cur) { cur->next = prev; prev = cur; cur = next; next = next->next; }

逆序后面部分的链表内容

ListNode* newhead1 = A; ListNode* newhead2 = prev; while(newhead2) { if(newhead1->val == newhead2->val) { newhead1 = newhead1->next; newhead2 = newhead2->next; } else { return false; } } return true; }

在赋值时我将A给newhead1我相信大家都能理解
把prev赋值给newhead2是将逆序后的头给newhead2
比较逆序后的部分,以newhead2为循环的终止条件
分为三种情况

正常情况如1221
中间为对称点情况12321
非回文情况1212

正常情况如1221下的newhead2应该在1221的第三个元素的位置及2的位置
这部分已经为逆置过的情况所以情况现在应该从1221变为两个1->2->2->NULL(注:这部分没错,在逆序时我们的第一个链表确实是这种情况,因为我们是将第三个元素的next置为空的)
第二个链表情况应该为1->2->NULL而我们的第一个链表.所以我们只需要比较从第二个链表的头到NULL即可.

中间为对称点的情况