Leetcode234-回文链表(2019 408源题)

题目：Leetcode234

解答：

基本思路：快慢指针找到中间结点+反转后半部分的链表

方法一：

bool isPalindrome(ListNode* head) {
        //找中间结点
        if(head == NULL || head->next == NULL) return true;//空结点也算回文链表
        ListNode* mid = head;
        ListNode* post = head;
        while(post->next != NULL && post->next->next != NULL)//while两个条件用&&
        {
            mid = mid->next;
            post = post->next->next;
        }
        //反转链表再比较
        mid->next = reverseList(mid->next);
        mid = mid->next;
        while(mid!=NULL){
            if(head->val == mid->val)
            {
                head = head->next;
                mid = mid->next;
            }else{
                return false;
            }
        }
        return true;
    }
    ListNode* reverseList(ListNode* head)
    {
        if(head == nullptr) return nullptr;
        ListNode* pre = nullptr;
        ListNode* post = head;
        while(head!=nullptr)
        {
            post = head->next;
            head->next = pre;
            pre = head;
            head = post;
        }
        return pre;
    }

时间复杂度：n；空间复杂度：1

16ms；-2.39%

方法二：递归解法——利用✨递归栈“先进后出”的特性来实现一个指针从后先前一个指针从前向后进行比较

ListNode* temp;
    bool isPalindrome(ListNode* head) {
        temp = head;
        return check(head);
    }
    bool check(ListNode* p)
    {
        if(p==nullptr) return true;//利用&的短路特性
        bool isPal = check(p->next) & (temp->val == p->val);//递归
        temp = temp->next;
        return isPal;
        
    }

时间复杂度：n；空间复杂度：n

16ms；-2.39%

总结

1.此题是2019年408数据结构部分应用题的源题

2.递归解法中有几个小技巧：(1) 利用&的短路特性来避免p为空指针 (2) “&与&&”的用法在两边是bool值的情况下一致——&是位运算符，&&是逻辑运算符；同理 | 为位运算符，|| 为逻辑运算符