请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？（leetcode原题）
拿到这个题的时候，看到给出的第二个示例以及要求O(1) 空间复杂度就知道要利用链表逆序思想，将链表后半部分逆序。然后从前到中和从后到中一一对比即可。
实现代码：
/**
* 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;
}
bool result = true;
struct ListNode* node1 = head;
struct ListNode* node2 = head;
struct ListNode* node3 = NULL;
//node2每次跳两步，node1每次跳一步，当node2->next或者node2->next->next为空时
//链表个数为奇数，node1就处在中间位置，
//链表个数为偶数，node1和node1->next就是中间两个位置。
while(node2->next!=NULL && node2->next->next !=NULL){
node2 = node2->next->next;
node1 = node1->next;
}
//逆序后半段链表
// 1->2->3->3->2->1
// 转为
// 1->2->3<-3<-2<-1
node2 = node1->next;
node1-> next = NULL;
while(node2!=NULL){
node3 = node2->next;
node2->next = node1;
node1 = node2;
node2 = node3;
}
node3 = node1;
node2 = head;
//从前端和后端开始对比数字
while(node2!=NULL && node1!=NULL){
if(node2->val != node1->val){
result = false;
break;
}
node2 = node2->next;
node1 = node1->next;
}
//在程序中应该把链表恢复原样，毕竟还有可能要用到这个链表，参照上面，这里就偷懒没写了
return result;
}
好久没有写算法了，为了链表的逆序在纸上画了半天才理清逻辑。。。
