题目

题目非常简单，无非就是判断一个没用头结点的指针，是否为回文链表，但是简单的题目往往值得更深的思考。该题目有很多的解法，想要在时间击败百分百的话，不仅仅是代码本身，可能跟电脑还有一定的关系。
全遍历，入数组：

思路很容易想到，第一次遍历完整个链表，一边遍历，一遍把节点入数组
并计算长度，最后用数组中的元素判断，规避了指针不能随意访问的难受
问题。时间:O(N)，空间:O(N)。

int q[70000];
bool isPalindrome(struct ListNode* head){struct ListNode* p = head;int len = 0;while(p){q[len++] = p->val;p = p->next;}for(int i = 1; i <= len/2; i++)if(q[i] != q[len-i+1]) return false;return true;
}

全遍历，入数组，做双向判断，其实就是对上面一个循环的改动。。

bool isPalindrome(struct ListNode* head) {int vals[50001], vals_num = 0;while (head != NULL) {vals[vals_num++] = head->val;head = head->next;}for (int i = 0, j = vals_num - 1; i < j; ++i, --j) {if (vals[i] != vals[j]) {return false;}}return true;
}

快慢指针，链表逆置：
设置快慢指针，都从头开始，快指针走每次走两步，慢指针每次走一步，那么慢指针最后要么到链表的中间元素，要么到元素中间元素的左边元素（这取决于链表长度为奇数还是偶数）。最后将前一段或者后一段逆置，判断。该方法有问题，在逆置完之后，如果在访问链表的话会出问题，因此，还需要将其翻转回来，但是题目没有要求不改变链表，我也就懒得写了，同理，可以在该方法机理上进行优化。实现略去翻转的步骤。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/bool isPalindrome(struct ListNode* head){// 特殊情况的排除if(head == NULL || head->next == NULL)return true;if(head->next->next == NULL){if(head->val == head->next->val)return true;elsereturn false;}struct ListNode *fastp, *slowp;fastp = head->next->next;slowp = head->next;while(fastp && fastp->next != NULL){fastp = fastp->next->next;slowp = slowp->next;}struct ListNode *prep, *nextp;prep = nextp = NULL;while(head != slowp){nextp = head->next;head->next = prep;prep = head;head = nextp;}if(fastp != NULL && fastp->next == NULL)slowp = slowp->next;while(prep != NULL){if(prep->val != slowp->val)return false;prep = prep->next;slowp = slowp->next;}return true;
}

快慢指针，入半栈：

优化上面的方案，省去了一半的循环，同时防止了链表结构的改变。结果
如下，完美。emm，也不是，空间是个问题，不过在这个空间爆炸，时间
有限的时代，谁又会在乎那点空间呢。

#define maxsize 100000
bool isPalindrome(struct ListNode* head){if(!head)//判除三种特殊情况 return true;if(!head->next)return true; if(!head->next->next)if(head->val!=head->next->val) return false;else 								 return true;struct ListNode *t=head,*q=head,*p=head;struct ListNode **stack=(struct ListNode **)malloc(sizeof(struct ListNode*)*maxsize);int top=-1;stack[++top]=t;while(p->next&&p->next->next){q=q->next;stack[++top]=q;p=p->next->next;}if(!p->next){//判断奇偶  奇数p->next为空，偶数不为空 for(int i=top;i>=0;i--,q=q->next){if(stack[i]->val!=q->val){return false;}}}else{q=q->next;for(int i=top;i>=0;i--,q=q->next){if(stack[i]->val!=q->val)return false;}}free(stack);return true;
}

链表反转：

思路新颖，可以自己尝试在本子上画一下，画出来是不难理解的。

bool isPalindrome(struct ListNode* head){if(head == NULL) return true;int len = 0;struct ListNode *p = head;while(p){len++;p = p->next;}if(len == 1) return true;if(len == 2){if(head->val == head->next->val) return true;else return false;}if(len == 3){if(head->next->next->val == head ->val) return true;else return false;}int tmp = (len-1)/2, flag = 0;if(len%2 == 1) flag = 1;len = (len+1)/2;p = head;while(len){head = head->next;len--;}struct ListNode *q = p, *r = p->next->next;p = p->next;q->next = NULL;while(tmp){p->next = q;q = p;p = r;r = r->next;tmp--;}if(flag == 1) q = q->next;while(head){if(q->val != head->val) return false;q = q->next, head = head->next;}return true;
}