链表的回文结构

清疚 2022-04-24 07:04 152阅读 0赞

## 回文链表 ##

*  在我们的生活中经常会碰到这种回文的结构，回文就是反转以后和以前一样的就是回文结构，例如 1->2->3->2->1，我们将它反转之后还是与原链表一样，我们就称这种链表结构为回文结构，那么如何来判断一个链表它是不是回文链表呢？
 *  解决方案  
    1、采用头插法将链表逆置，将整个链表反转过来，判断是否与原链表一样即可  
    2、升级版：既然它要是回文结构，我们只需要将链表的一半逆置即可，采用双指针遍历的方式，一个从前往后，一个从后往前，同时遍历并比较链表元素是否相等即可。
 *  在这里我来说一下第二种方法的具体思路  
    （1） 第一步，先求出链表的总长度  
    （2） 第二步，找到中间节点  
    （3） 第三步，逆置链表后半部分节点  
    （4） 第四步，判断链表是否是回文结构

#include<iostream>
    
    using namespace std;
    
    typedef struct ListNode
    {
    	int value;
    	struct ListNode* next;
    }ListNode;
    
    bool isPalindrome(ListNode* head) 
    {
    	// 求链表长度
    	int len = 0;
    	for (ListNode *cur = head; cur != NULL; cur = cur->next) {
    		len++;
    	}
    
    	// 找到链表的中间结点
    	ListNode *middle = head;
    	for (int i = 0; i < len / 2; i++) {
    		middle = middle->next;
    	}
    
    	// 逆置链表的后半部分
    	ListNode *node = middle;
    	ListNode *rhead = NULL;
    	while (node != NULL) {
    		ListNode *next = node->next;
    
    		node->next = rhead;
    		rhead = node;
    
    		node = next;
    	}
    
    	// 判断是否是回文
    	ListNode *p1 = head;
    	ListNode *p2 = rhead;
    	while (p1 != NULL && p2 != NULL) {
    		if (p1->value != p2->value) {
    			return false;
    		}
    
    		p1 = p1->next;
    		p2 = p2->next;
    	}
    
    	return true;
    }
    
    //尾插法建立链表
    void PushBack(ListNode* head, int v)
    {
    	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    	node->value = v;
    	if (head == NULL)
    	{
    		head = node;
    		node->next = NULL;
    	}
    	else
    	{
    		ListNode* cur = head;
    		while (cur->next != NULL)
    		{
    			cur = cur->next;
    		}
    		cur->next = node;
    		node->next = NULL;
    	}
    }
    
    int main()
    {
    	ListNode* p = NULL;
    	PushBack(p, 1);
    	PushBack(p, 2);
    	PushBack(p, 3);
    	PushBack(p, 2);
    	PushBack(p, 1);
    	cout << isPalindrome(p) << endl;
    	system("pause");
    	return 0;
    }

这道题其实就是让你实现一下如何将一个链表反转，类似的还有很多，比如让你判断一个数，一个字符串是否具有回文结构，道理其实都差不多，这里我介绍的就是链表反转的基本操作，当然对于这种题型我们还有很多种方法去解决它，比如我们所学的栈的特性，先进后出，利用栈的这种特性，我们可以让一半先进栈然后再让其出栈与剩下的比较即可。其实进栈，出栈就是一个很常见的反转操作哦!