题目描述

请判断一个链表是否为回文链表。

样例

输入: 1->2
输出: false

算法1

(双指针+原地操作) $O(n)$

参考文献

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
//时间复杂度 0(N) 空间复杂度 O(1)
public:
    bool isPalindrome(ListNode* head) {
        //创建虚拟节点 并让头结点指向head 可以解决奇数偶数的判断
        // 链表长度是奇数slow指向最中间的前一个
        //偶数的话 指向链表中间偏左的那个
        ListNode *node = new ListNode(-1);node->next=head;
        // 创建快慢节点 用于遍历一次 找到 中间节点 
        ListNode *slow  = node,*fast = node;
        while(fast&&fast->next){
            slow = slow->next;// 结束以后 slow是在中间
            fast = fast->next->next;// 在末尾是在中间  
        }
        // 将slow以后的链表进行反转  prev 指向null 这个是链表反转的基本操作
        slow = slow->next;ListNode *prev = nullptr;
        while(slow){
            ListNode * temp = slow->next;
            slow->next = prev;
            prev = slow;
            slow = temp;
        }
        // prev指向尾结点 此时必须使用prev 也可以使用head 进行判断
        while(prev){
            if(prev->val!=head->val) return false;
            prev = prev->next;head=head->next;
        }
        return true;

    }
};

```