首页 / 算法 / [算法]回文检测

[算法]回文检测

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了[算法]回文检测，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1511字，纯文字阅读大概需要3分钟。

内容图文

链表的回文检测

有关链表的回文检测，用到的就是链表操作中常常用到的双指针的方法，找到链表的中点位置，然后依次对比两边的结点。但是在找链表的中点的时候要注意链表的总个数是偶数或者奇数的两种情况。

1.找链表的中点位置，并把中点以前的各个结点的值存入到栈中。
2.针对偶数或者奇数个链表结点，对中点结点做一个小的调整。
3.依次对比栈中结点的值后链表后半部分结点的值是否相等，决定是否是回文结构。

代码实现：

bool isPalindrome(ListNode* head) 
{
	bool isPalindrome = true;
	if(head == NULL)
	{
		return true;
	}
	
	stack<int> s;
	
	//找到链表的中点
	ListNode *fast = head;
	ListNode *low = head;
	while(fast != NULL && fast->next != NULL)
	{
		s.push(low->val);
		fast = fast->next->next;
		low = low->next;
	}//while
	if(fast != NULL)
	{
		low = low->next;
	}
	
	//对比前后两段链表的内容
	while(low != NULL)
	{
		if(low->val != s.top())
		{
			isPalindrome = false;
			break;
		}
		low = low->next;
		s.pop();
	}//while
	
	return isPalindrome;
}

这种方法能够实现O(n)的时间复杂度，但是他的空间复杂度同样是O(n).

链表判断回文O(1)空间复杂度

对链表的后半部分逆序，这样就能一次对比前半部分和后半部分的不同了。

bool isPalindrome(ListNode* head) 
{
	if(head == NULL || head->next == NULL)
		return true;
		
	ListNode *fast = head;
	ListNode *low = head;
	
	//利用快慢指针找到链表的中点
	while(fast != NULL && fast->next != NULL)
	{
		fast = fast->next->next;
		low = low->next;
	}
	if(fast != NULL)
	{
		low = low->next;
	}
	
	//逆序链表的后半部分
	ListNode dummy(-1);
	dummy.next = low;
	while(low->next != NULL)
	{
		ListNode *tmp = low->next;
		low->next = tmp->next;
		tmp->next = dummy.next;
		dummy.next = tmp;
	}//while
	
	//对比前后两部分
	low = dummy.next;
	fast = head;
	while(low != NULL)
	{
		if(fast->val != low->val)
			return false;
		low = low->next;
		fast = fast->next;
	}
	
	return true;
}

原文：http://www.cnblogs.com/stemon/p/4817100.html

内容总结

以上是互联网集市为您收集整理的[算法]回文检测全部内容，希望文章能够帮你解决[算法]回文检测所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1301500.html

来源：【匿名】