[LeetCode]234.Palindrome Linked List

本文主要是介绍[LeetCode]234.Palindrome Linked List，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

Given a singly linked list, determine if it is a palindrome.

Follow up:
Could you do it in O(n) time and O(1) space?

思路

利用双指针法找到链表中点位置，链表中点以后的的元素（不包括中点元素）翻转，再跟链表中点位置以前的元素一一匹配。

代码

/*---------------------------------------
*   日期：2015-07-18
*   作者：SJF0115
*   题目: 234.Palindrome Linked List
*   网址：https://leetcode.com/problems/palindrome-linked-list/
*   结果：AC
*   来源：LeetCode
*   博客：
-----------------------------------------*/
#include <iostream>
#include <vector>
using namespace std;struct ListNode{int val;ListNode *next;ListNode(int x):val(x),next(NULL){}
};class Solution {
public:bool isPalindrome(ListNode* head) {if(head == nullptr){return true;}//if// 中点位置ListNode* slow = head;ListNode* fast = head->next;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}//whileslow = slow->next;// 翻转ListNode* q = ReverseList(slow);// 判断是否是回文串ListNode* p = head;while(p && q){if(p->val != q->val){return false;}//ifp = p->next;q = q->next;}//whilereturn true;}
private:// 翻转ListNode* ReverseList(ListNode* head){if(head == nullptr){return head;}//if// 头结点ListNode* dummy = new ListNode(-1);ListNode* p = head;ListNode* nextNode = p->next;while(p){nextNode = p->next;p->next = dummy->next;dummy->next = p;p = nextNode;}//whilereturn dummy->next;}
};int main(){Solution s;ListNode* head = new ListNode(1);ListNode* node2 = new ListNode(2);ListNode* node3 = new ListNode(3);ListNode* node4 = new ListNode(4);ListNode* node5 = new ListNode(3);ListNode* node6 = new ListNode(2);ListNode* node7 = new ListNode(1);head->next = node2;node2->next = node3;node3->next = node4;node4->next = node5;node5->next = node6;node6->next = node7;bool result = s.isPalindrome(head);if(result){cout<<"是回文串"<<endl;}//ifelse{cout<<"不是回文串"<<endl;}//elsereturn 0;
}