题目描述

算法1

C++ 代码

/**
 * 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) {
    //快慢指针找中点
     ListNode *slow,*fast;
     slow = fast = head;
     while(fast!=nullptr && fast->next!=nullptr){
         fast = fast->next->next;
         slow = slow->next;
     }
     //如果fast指针没有指向null，说明链表长度为奇数，slow还要再前进一步,反之
     if(fast!=nullptr) slow = slow->next;
     //从slow开始反转后面的链表，现在就可以开始比较回文串了：
     ListNode *right = head;
     ListNode *left = revese(slow);
     while(right!=nullptr &&left!=nullptr){
         if(left->val!=right->val) return false;
         left = left->next;
         right = right->next;
     }
     return true;


    }
    ListNode *revese(ListNode *head){
        if(!head || !head->next) return head;
        ListNode*last = revese(head->next);
        head->next->next=head;
        head->next = nullptr;
        return last;
    }
};

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla