【 声明：版权所有，转载请标明出处，请勿用于商业用途。 联系信箱：libin493073668@sina.com】
题目链接：?rp=1&ru=/ta/cracking-the-coding-interview&qru=/ta/cracking-the-coding-interview/question-ranking
题目描述请编写一个函数，检查链表是否为回文。给定一个链表ListNode* pHead，请返回一个bool，代表链表是否为回文。测试样例：{1,2,3,2,1}返回：true{1,2,3,2,3}返回：false思路我们有两种方法，比较容易想到的方法应该是使用栈保存前一半的结点，然后对于后一半的结点再一个个的与栈内的结点比较是否相等还有一种方法就是无需额外开辟空间，我们可以直接将后一串翻转，，然后再两端比较
1.使用栈
/*struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}};*/class Palindrome{public:bool isPalindrome(ListNode* pHead){// write code hereif(pHead == nullptr || pHead->next==nullptr)return true;stack<ListNode*> S;ListNode *fast = pHead;ListNode *slow = pHead;while(fast && fast->next){S.push(slow);fast = fast->next->next;slow = slow->next;}if(fast)slow = slow->next;while(slow){if(slow->val!=S.top()->val)return false;slow = slow->next;S.pop();}return true;}};2.翻转
/*struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}};*/class Palindrome{public:bool isPalindrome(ListNode* pHead){// write code hereif(pHead == nullptr || pHead->next==nullptr)return true;ListNode *fast = pHead;ListNode *slow = pHead;while(fast && fast->next){fast = fast->next->next;slow = slow->next;}if(fast){slow->next = reverseList(slow->next);slow = slow->next;}else{slow = reverseList(slow);}while(slow){if(slow->val!=pHead->val)return false;slow = slow->next;pHead = pHead->next;}return true;}ListNode *reverseList(ListNode *pHead){if(pHead==nullptr)return nullptr;ListNode *pNode = pHead;ListNode *newHead = nullptr;ListNode *pPre = nullptr;while(pNode){ListNode *pNext = pNode->next;if(pNext==nullptr)newHead = pNode;pNode->next = pPre;pPre = pNode;pNode = pNext;}return newHead;}};
版权声明：本文为博主原创文章，如果转载，请注明出处
不做任何解释。没有人明白，
