234. Palindrome Linked List

请看题

解法

这道题可以用快慢指针来解决，那么问题来了，什么是快慢指针呢牢大？

问的很好，简单来说，快慢指针就是两个不同速度的指针

牢大你说的好像是废话啊

哈哈，快慢指针就是两个不同的指针用不同的速度去移动。比如说，一个链表，快指针一次会移动两个节点，而慢指针会移动一个节点。而快指针移动到终点的时候慢指针才移动到一半。

那么知道了这个跟我解题又有什么关系呢？

关系可大了，这道题用快慢指针的解法是最棒的！

我们只需要定义几个指针变量就能完美的解决这道题。

先来定义快指针和慢指针，快指针一次移动两个，慢指针一次移动一个。那么使用一个while循环，当快指针移动到终点的时候或者终点-1节点的时候就应该停下来了。这时候的慢指针才刚刚到一半。

如果快指针超出了终点（终点+1), 慢指针需要格外的移动一次。

接下来就很简单了，因为慢指针已经到了链表的中间节点，我们只需要反转一下慢指针链表的内容再和原来的链表比较一下就能够得出这道题的答案了。

最后附上答案

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(!head || !head->next) { return true; }
        ListNode *slow = head;
        ListNode *fast = head;

        while(fast && fast->next){
            slow = slow->next;
            fast = fast->next->next;
        }

        if(fast){
            slow = slow->next;
        }

        ListNode *prev = nullptr;
        ListNode *current = slow;
        while(current){
            ListNode *next = current->next;
            current->next = prev;
            prev = current;
            current = next;
        }

        ListNode *firstHalf = head;
        ListNode *secondHalf = prev;
        while(secondHalf){
            if(firstHalf->val != secondHalf->val){
                return false;
            }
            firstHalf = firstHalf->next;
            secondHalf = secondHalf->next;
        }
        return true;
    }
};