【程序员金典】回文链表

本文主要是介绍【程序员金典】回文链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述
请编写一个函数，检查链表是否为回文。
给定一个链表ListNode* pHead，请返回一个bool，代表链表是否为回文。
测试样例：
{1,2,3,2,1}
返回：true
{1,2,3,2,3}
返回：false

c++代码

方法一：
链表前半部分入栈，后半部分与栈中的元素比较

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class Palindrome {
public:bool isPalindrome(ListNode* pHead) {// write code here//快慢指针找到链表的中间节点stack<int> tmp;ListNode* slow=pHead,*fast=pHead;while(fast!=nullptr&&fast->next!=nullptr){tmp.push(slow->val);slow=slow->next;fast=fast->next->next;}if(fast!=nullptr)//奇数个slow=slow->next;while(slow!=nullptr){if(tmp.top()!=slow->val)return false;elsetmp.pop();slow=slow->next;}return true;}
};

方法二：

反转链表，其实只需要找到链表的中点，然后将中点后面的部分反转。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:bool isPalindrome(ListNode* head) {if(head==NULL||head->next==NULL)return true;//取中点的位置，后半段进行反转，然后再比较ListNode *slow=head,*fast=head;//采用快慢指针找到中点的位置，slow每次前进一步，fast每次前进两步,当fast不能再往前走的时候，slow正好到前半段的//最后一个位置while(fast->next&&fast->next->next){slow=slow->next;fast=fast->next->next;}slow->next = reverseList(slow->next);slow = slow->next;while(slow != NULL){if(head->val != slow->val)return false;head = head->next;slow = slow->next;}return true;
}ListNode* reverseList(ListNode *head)
{ListNode *pre = NULL;ListNode *next = NULL;while(head != NULL){next = head->next;head->next = pre;pre = head;head = next;}return pre;
}
};