题目描述

Given a singly linked list, determine if it is a palindrome.
题意：给一个链表，判断一个链表是否是回文链表。

样例

Input: 1->2->2->1
Output: true

算法1

反转链表

题解：考虑我们判断一个字符串是否时回文串的时候，我们需要从首尾向中间遍历，但是链表是单向的，我们该怎么办呢？我们可以先把链表的后半部分反转过来，然后使用双指针就可以了。可以先用 Leetcode806题876. Middle of the Linked List 找到链表中间元素、然后使用Leetcode206题 反转后半部分链表即可。

C++ 代码

    bool isPalindrome(ListNode* head) {
        if(head == NULL || head->next == NULL) return true;
        ListNode* slow = head;
        ListNode* quick = head;
        //使用快慢指针找到数组的后半部分第一个指针
        while(quick != NULL && quick->next != NULL)
        {
            slow = slow->next;
            quick = quick->next->next;
        }
        //通过迭代法来反转后半部分链表
        ListNode* pre = NULL;
        ListNode* cur = slow;
        while(cur != NULL)
        {
            ListNode* temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        //此时的pre指向的链表最后一个节点
        while(pre != NULL)
        {
            if(pre->val != head->val)
                return false;
            pre = pre->next;
            head = head->next;
        }
        return true;
    }