淘先锋技术网

首页 1 2 3 4 5 6 7

题目要求

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

示例:
输入:1->2->2->1
输出:是

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

解题思路

方法一:
将链表存储在数组里,再首尾判断,空链表也是回文链表,另外分配了空间,空间复杂度不为常数,此处不做赘述
方法二:
逆置后半部分链表,前半部分链表指向空,后半部分逆置链表指向空,进行比较,逆置时先找到中间位置,再逆置后半部分链表,逆置后返回后半部分逆置后第一个元素

解题演示

输入:1->2->2->1
输出:是

过程显示:
方法二:

  • 先用快慢指针找出中间节点,前面有相关的博客,此处不详细写
  • 将中间节点后的指针反转,这个内容前面博客也有相关讲解
  • 最后从头、尾指针向中间遍历,判断是否是回文

解题代码

方法二:

classPalindromeList{
public:
	bool chkPalindrome(ListNode* A) {
		if (A == NULL)
		{
			return false;
		}
		elseif(A->next == NULL)
		{
			return true;
		}
		//快慢指针找出中间节点        
		ListNode* fast = A;
		ListNode* slow = A;
		while (fast != NULL && fast->next != NULL)
		{
			fast = fast->next->next;
			slow = slow->next;
		}
		//将中间节点后的指针反转  
		ListNode* p = slow->next;
		ListNode* p1 = slow->next->next;
		while (p != NULL)
		{
			p->next = slow;
			slow = p;
			p = p1;
			p1 = p1->next;
		}
		//从头、尾指针向中间遍历,判断A是否是回文  
		while (A != slow)
		{
			if ((A->val) != (slow->val))
			{
				return false;
			}
			else
			{
				if (A->next == slow)
				{
					return true;
				}
				A = A->next;
				slow = slow->next;
			}
		}
		return true;
	}
};