链表之第二回-Toy模板网

这篇具有很好参考价值的文章主要介绍了链表之第二回。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

链表之第二回,链表之108回,链表,数据结构

欢迎来到我的：世界

该文章收入栏目：链表

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

前言

对于我来说这个博客是一个学习的地方，就像我的上篇文章一样，有老铁们的支持，陪伴；我很满足，这个栏目我会继续坚持下去，108回，就像我的108难一样，只要撑过磨难，一定能取到真经；

--------------------------对过程全力以赴，对结果淡然处之

第一题：反转一个链表

地址：oj地址

链表之第二回,链表之108回,链表,数据结构
解题思路：

思路：让链表翻转过来，可以先创造一个新的链表头指针指向空，然后原来的链表一个一个头插到新的指针，到时候在返回新创造的链表起始位置。按照这个思路；

我们需要创造一个新指针变量指向空：

然后接下来就是将原链表头插入newnode；

这里需要注意一下：如果按照头插入newnode,如果指针pHead将结点插入来的话，那pHead原指向的下一个结点就丢失了，所以这里需要创造一个新的指针 next 存放pHead所指的下一个结点，这样才能找回去；

后面步骤依次将后续头插入；这里有一步也需要注意，记得让cur找回到next的结点，然后使next再指向cur下一个结点；

直到pHead为空结束，最后返回newnode；

代码：

struct ListNode* ReverseList(struct ListNode* head ) {
    // write code here
    struct 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地址

链表之第二回,链表之108回,链表,数据结构

加强版的反转链表；

思路：
先利用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 here
	if (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地址

链表之第二回,链表之108回,链表,数据结构

首先我们要知道什么是回文结构：
如

偶数回文：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 here
        struct 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 here
    struct 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;
}