LeetCode234 回文链表

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

题面

输入是一个链表，输出是一个布尔值，表示链表是否回文。

解法

链表解法的一个综合运用
用快慢指针找出链表中点，再将链表的后半部分反转，比较两部分是否相同

代码

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* slow = head, *fast = head;
        while(fast -> next != nullptr && fast -> next -> next != nullptr) {
            slow = slow -> next;
            fast = fast -> next -> next;
        }
        slow -> next = reverseList(slow -> next);
        slow = slow -> next;
        while(slow) {
            if (head -> val != slow -> val) {
                return false;
            }
            head = head -> next;
            slow = slow -> next;
        }
        return true;
    }
    // 翻转链表
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        while(head != nullptr) {
            ListNode* cur = head -> next;
            head -> next = prev;
            prev = head;
            head = cur;
        }
        return prev;
    }
};