234. Palindrome Linked List.md

234. Palindrome Linked List

思路

判断所给链表是不是回文的，要求线性时间复杂度且空间复杂度为O(1)。
可以考虑现将链表的后半部分（或前半部分）反转一下，然后再设置两个指针p和q，初始分别指向前、后半部分的第一个节点，然后同时往后移动并判断值是否相等。

/**
 * 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) {
        ListNode *p = head, *q, *tmp;
        int count = 0;
        while(p){
            count++;
            p = p -> next;
        }
        if(count <= 1) return true; // 若链表长度不超过1则肯定是回文的
        
        p = head;
        for(int i = 1; i < count/2; i++) p = p -> next;
        if(count % 2 == 1) p = p -> next; // 链表长为奇数，p需要再往后移动一个节点
        // 此时p指向后半部分的第一个节点的前一个节点
        
        // 迭代法翻转后半部分链表
        q = p -> next; // 此时q指向后半部分的第一个节点
        p -> next = NULL;
        while(q){
            tmp = q -> next;
            q -> next = p -> next;
            p -> next = q;
            q = tmp;
        }
        

        q = p -> next; // q指向后半部分的第一个节点
        p = head; // p指向前半部分的第一个节点
        for(int i = 0; i < count/2; i++){
            if(p -> val != q -> val) return false;
            p = p -> next;
            q = q -> next;
        }
            
        return true;  
    }
};