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

链表之第二回

news 2025/7/14 6:58:58

在这里插入图片描述

欢迎来到我的：世界

该文章收入栏目：链表

希望作者的文章对你有所帮助，有不足的地方还请指正，大家一起学习交流 !

前言

对于我来说这个博客是一个学习的地方，就像我的上篇文章一样，有老铁们的支持，陪伴；我很满足，这个栏目我会继续坚持下去，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指针指向的是head，prve先是指向空，开始找区间起始位置，根据m值(m为2，则应该找第二个结点)，每找过一个节点，将cur给到prve(这是为了判断区别出是不是从头就开始头插，在后面链接时会用来判断其链接的方式，在上面有详细解释)，直到找到区间起始(如果m=1，则直接从第一个进行头插，这个时候的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 count=m;struct ListNode*prev=NULL;while(count-->1){prev=cur;cur=cur->next;}struct ListNode*ret=cur;//进行头插反转int len=n-m+1;while(len--){struct ListNode*next=cur->next;cur->next=newnode->next;newnode->next=cur;cur=next;}//链接if(prev==NULL){head=newnode->next;ret->next=cur;}else {prev->next=newnode->next;ret->next=cur;}
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* newnode=NULL;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;
}