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?
判断一个链表是否为回文链表，有很多方法都可以进行判断，可以先遍历链表然后将值全部存储到vector之中，也可以遍历链表然后将list中的值都压倒堆栈中再和List进行比较，
但是想要达到题目上面的 时间复杂度为O（n），而空间复杂度为O（1）还要用到递归：
首先是不用递归的方法（使用一个栈）：
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution { 10 public: 11 bool isPalindrome(ListNode* head) { 12 ListNode * tmpHead = head; 13 stack<int> lt; 14 while (tmpHead){ 15 lt.push(tmpHead->val); 16 tmpHead = tmpHead->next; 17 } 18 19 while (!lt.empty()){ 20 if (head->val != lt.top()) return false; 21 lt.pop(); 22 head = head->next; 23 } 24 return true; 25 } 26 };
首先上面这个空间复杂度是不满足要求的，再者，既然想到了将元素压入栈中，那么结合递归的话，应该就能做到空间复杂度O（1）了，应为上面的方法用到了堆栈，与递归能很好的结合：
1 class Solution{ 2 private: 3 ListNode * theHead; 4 5 public: 6 bool isPalindrome(ListNode* head) { 7 theHead = head; //先将head保存到一个theHead里面，便于与后面的递归了得指针相比较。 8 return valid(head); 9 } 10 11 bool valid(ListNode * first) 12 { 13 if (first == NULL) return true; 14 if (valid(first->next) == false) return false; 15 if (first->val == theHead->val){ 16 theHead = theHead->next; 17 return true; 18 } 19 else 20 return false; 21 } 22 };
因为道理比较简单，所以就不一一赘述了。
LeetCode OJ：Palindrome Linked List（回文链表判断）
原文：http://www.cnblogs.com/-wang-cheng/p/4862236.html