leetcode 234. Palindrome Linked List （判断链表是否回文）

题目要求

给定一个单链表，判断是否是回文链表。
O(n) time and O(1) space.

输入示例

// Example 1:
Input: 1->2
Output: false
// Example 2:
Input: 1->2->2->1
Output: true

解题思路

本题和相关题目解答leetcode 9. Palindrome Number(判断是不是回文数)
解答leetcode 125 Valid Palindrome(判断回文字符)的思想是一致的，反转后再比较，但还是由于存储位置不连续，所以没办法向数组那样进行直接操作，所以为了节省时间。

我们用一个技巧，使用快慢指针，先遍历到链表的中间，然后反转链表的后半部分，之后和原链表的头部元素开始比较是否相等，从而判断是否回文，这里可能有点绕，通过下边的图，仔细想想。

主要代码 c++

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
    
public:bool isPalindrome(ListNode* head) {
    if(head == NULL|| head->next==NULL) return true;ListNode *slow = head;ListNode *fast = head;while(fast->next && fast->next->next) //第一步快慢找中点{
    slow = slow->next;fast = fast->next->next;}ListNode *pre = NULL, *cur= slow,*next;while(cur) //第二步反转链表{
    next = cur->next;cur->next = pre;pre = cur;cur = next;}while(pre->next) //第三步判断回文{
    if(head->val != pre->val)return false;head = head->next;pre = pre->next;}  return true;}
};

知识点：

本题一些方法在下面的题目中也有涉及到过：
翻转
解答：leetcode 206. Reverse Linked List (翻转一个链表)
回文：
解答leetcode 9. Palindrome Number(判断是不是回文数)
解答leetcode 125 Valid Palindrome(判断回文字符)

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