您现在的位置是：首页 >其他 >【数据结构】--单链表力扣面试题⑥链表的回文结构网站首页其他

题述：对于一个链表，请设计一个时间复杂度为o(n),额外空间复杂度为o(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度<=900

测试样例：

输入：1->2->2->1

输出：true

题目分析：

回文就是对称结构。题目所让求解的肯定是在单链表的前提下，要是双链表就很好求了，但是单链表的缺陷就是不能倒着走，只能正着走。

有一种想法是，创建数组大小900的数组，如int a[900],然后遍历链表，把每个节点的值都放入此数组中，用数组来判断回文。这样做oj上是能跑过的，但是不可行，因为这种方法的空间复杂度是o(n)，因为你链表开多长你数组就得开多大去存储，这是一个侥幸方法。

正确的思路：

①、找链表的中间节点，偶数个结点就找后一个。至于怎么找，我之前代码有写过

②、将指向链表中间节点的指针（包括本身）后面的所有节点逆置，如果和中间节点之前的节点内容相同，那就符合回文结构

③、找到中间节点后，即使逆置，还可以使中间节点的前一个节点指向中间节点，可以不用解开（改变指向），因为不解开（不改变指向）也可以判断是否为回文结构，相反如果解开链表，会更麻烦。

//判断链表的回文结构
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

struct ListNode
{
	int val;
	struct ListNode* next;
};
//1、找中间节点的函数
struct ListNode* middleNode(struct ListNode* head)
{
	struct ListNode* slow, * fast;
	fast = slow = head;
	while (fast && fast->next)
	{
		slow = slow->next;
		fast = fast->next->next;
	}
	return slow;
}
//2、逆置链表的函数
struct ListNode* reverseList(struct ListNode* head)
{
	struct ListNode* n1, * n2, * n3;
	n1 = NULL;
	n2 = head;
	n3 = n2->next;
	while (n2)
	{
		n2->next = n1;
		n1 = n2;
		n2 = n3;
		if (n3)
		{
			n3 = n3->next;
		}
	}
	return n1;
}
bool chkPalindrome(struct ListNode* A)
{
	struct ListNode* mid = middleNode(A);//找到中间节点
	struct ListNode* rHead = reverseList(mid);//将中间节点（包括本身）后的节点翻转
	struct ListNode* curA = A;
	struct ListNode* curR = rHead;
	while (curA && curR)//因为对于有偶数个结点来说，curR会先碰到NULL，作为结束标志
	{//所以这里判断条件只写curR即可，在是回文的前提下。因为奇数节点时，curA和curR同时为空，
     //偶数是curR先为空
		if (curA->val != curR->val)
		{
			return false;
		}
		else
		{
			curA = curA->next;
			curR = curR->next;
		}
	}
	return true;
}
int main()
{
	struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));

	n1->val = 1;
	n2->val = 2;
	n3->val = 3;
	n4->val = 2;
	n5->val = 1;

	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = n5;
	n5->next = NULL;

	int Istrue = chkPalindrome(n1);
	printf("该链表是否为回文结构:(1真/0假)%d", Istrue);

	return 0;
}