淘先锋技术网

首页 1 2 3 4 5 6 7

题目描述

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

在这里插入图片描述

思路

我们需要找到传入链表的中间结点,并将中间结点及其后面结点进行反转,然后再将原链表的前半部分与反转后的后半部分进行比较,若相同,则该链表是回文结构,否则,不是回文结构。

1.找到链表的中间结点。
在这里插入图片描述
2.反转中间结点及其后面的结点。
在这里插入图片描述
3.比较链表的前半部分与后半部分的结点值,若相同则是回文结构,否则,不是回文结构。
在这里插入图片描述
将A指针指向的结点与RHead指针指向的结点进行比较,若相同,则两个指针后移,继续比较后面的结点,直到RHead指针指向NULL时,比较结束。

注意:就算传入的链表是结点数为奇数的回文结构,该思路也可以成功判断。
例如,以下链表反转其后半部分后,我们看似链表应该是这样的。
在这里插入图片描述
但反转后的链表并不是这样的,而应该是下面这样:
在这里插入图片描述
因为我们反转的是中间结点及其后面的结点,并没有对前面的结点进行任何操作,所以结点5所指向的结点应该还是结点7。

于是该链表的比较过程应该是这样的:1等于1,3等于3,5等于5,7等于7,然后RHead指针指向NULL。所以判断该链表是回文结构。

代码实现

struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
}; 

class PalindromeList {
public:
	//查找链表的中间结点
	struct ListNode* middleNode(struct ListNode* head)
	{
		struct ListNode* fast = head;//快指针
		struct ListNode* slow = head;//慢指针
		while (fast&&fast->next)//遍历继续的条件
		{
			slow = slow->next;//慢指针一次走一步
			fast = fast->next->next;//快指针一次走两步
		}
		return slow;//返回慢指针
	}
	//反转链表
	struct ListNode* reverseList(struct ListNode* head)
	{
		struct ListNode* cur = head;//记录当前待头插的结点
		struct ListNode* newhead = NULL;//新链表初始时为空
		while (cur)//链表中结点头插完毕时停止循环
		{
			struct ListNode* next = cur->next;//记录下一个待头插的结点
			cur->next = newhead;//将结点头插至新链表
			newhead = cur;//新链表头指针后移
			cur = next;//指向下一个待头插的结点
		}
		return newhead;//返回反转后的头指针
	}
	bool chkPalindrome(ListNode* A) {
		ListNode* mid = middleNode(A);//查找链表的中间结点
		ListNode* RHead = reverseList(mid);//反转后半段链表
		while (RHead)//比较结束的条件
		{
			if (A->val != RHead->val)//不是回文结构
				return false;
			A = A->next;//指针后移
			RHead = RHead->next;//指针后移
		}
		return true;//是回文结构
	}
};

注:链表的中间结点反转链表的题目已经讲述过,在此就不再过多论述。