LeetCode 234. 回文链表

题目链接：https://leetcode-cn.com/problems/palindrome-linked-list/

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false
示例 2:

输入: 1->2->2->1
输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

大致思路就是：（查找链表中间结点和反转链表的组合）具体来说就是先找到中间结点，然后再反转一半链表，我选的是反转前半部分，最后再遍历比较前后部分的值是否相等，从而判断这个链表是否为回文链表。

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     struct ListNode *next;
 6  * };
 7  */
 8 bool isPalindrome(struct ListNode* head){
 9     if(head==NULL||head->next==NULL) return true;
10     
11     //第一部分 用快慢指针先找到链表中间结点
12     struct ListNode *slow=head;
13     struct ListNode *fast=head;
14     int sum=0;
15     while(fast&&fast->next!=NULL){
16         slow=slow->next;
17         fast=fast->next->next;
18         sum++;
19     }
20     if(fast&&fast->next==NULL) slow=slow->next;
21     
22     //第二部分 反转链表 这里反转的是前半部分链表
23     struct ListNode* pre=NULL;
24     struct ListNode* cur=head;
25     while(sum--){
26         struct ListNode* temp=cur->next;
27         cur->next=pre;
28         pre=cur;
29         cur=temp;
30     }
31     
32     //第三部分 前后部分链表依次遍历比较 从而判断是否为回文链表
33     while(pre){
34         if(pre->val!=slow->val) return false;
35         pre=pre->next;
36         slow=slow->next;
37     }
38     return true; 
39 }