Problem：Given a singly linked list, determine if it is a palindrome.
题目很简单，比较字符串是否为回文。思路就是依次比较对称位置上的数对是否相等。数据结构为单链表：
1 struct ListNode { 2 int val; 3 ListNode *next; 4 ListNode(int x) : val(x), next(NULL) {} 5 };
方法一：首先想到的是最无趣的办法。指针p从前向后遍历，直到中间节点，p每后移一位，q就从头结点开始移到与p相对称的位置，进行比较。
方法二：稍稍优化一下，将链表的尾结点的next指针指向链表的中间节点，即链表的后半部分成为一个循环链表，这样，指针p从前向后遍历，直到中间节点，p每后移一位，q就从当前位置后移1/2n-1（假设n为偶数，奇数的情况类似），进行比较。
以上两个方法的时间复杂度O(n2)，原因在于单链表难以找到上一节点。那么能否只将链表从前往后遍历一遍就可以比较了呢？
方法三：由于顺序表很容易找到上一节点，很显然可以找到中间节点，指针p从第一个节点开始，遍历前一半时，将数据导出为一个顺序表，然后遍历后一半，一一比较。（也可将其想成一个栈，遍历前一半的时候一一压栈，遍历后一半时，如果当前位置和栈顶元素相同，出栈，否则，返回false）
代码如下：
int getLength(ListNode* head){ ListNode* p = head; int length = 0; while (p) { p = p->next; length++; } return length; } class Solution { public: bool isPalindrome(ListNode* head) { //寻找中间节点 int l = getLength(head); int n = l % 2 ? ( l + 1 ) / 2 : ( l / 2 + 1 ); //构造栈s，给其赋值 int* s = new int[n]; ListNode* p = head; for (int i = 0; i < n - 1; i++, p = p->next) { s[i] = p->val; } //m是栈顶元素的下标，p指向和栈顶元素对称的节点 p = l % 2 ? p->next : p; int m = n - 2; while (p && ( m >= 0 ) ) { //如果栈顶元素和当前节点p的值不一样，返回false if(s[m] != p->val) return false; //否则弹出栈顶元素，p后移一位 m--; p = p->next; } return true; } };
但是这种做法的缺点在于空间复杂度为O(n)。
然而以上两点洒家并木有想到:-( ，具体思路和代码可移步此处。
原文：http://www.cnblogs.com/zizhao/p/4875950.html