20-回文链表

自己的做法

算法思想

可以遍历链表，把元素依次放入数组，然后使用两个指针一前一后来进行判断。但是该算法的时间复杂度是$O(n)$，空间复杂度也是$O(n)$。不够好。

可以将后半段链表反转，然后和前半段链表比较。然后再恢复为原来的链表(可以不恢复，但~ 恢复回来是个好的习惯)。

1. 找到前半段链表的最后一个节点。通过快慢指针方法。
2. 反转后半段链表
3. 进行比较
4. 将链表恢复

找到前半部分链表的尾节点

使用快慢指针法。

通过两个指针slow和fast，开始都指向head。

然后slow向后走一步，fast向后走两步。当fast->next == nullptr || fast->next->next == nullptr时，循环结束。

此时slow指向的就是前半部分链表的尾节点。

反转后半部分链表

之前也做过反转链表的题目，直接使用该算法即可。

使用两个指针cur和pre，初始cur指向head，pre指向null。

然后开始循环：

1. 创建局部变量temp = cur->next，来保存下一个节点
2. cur指向的结点的next指向pre
3. pre = cur
4. cur = temp

当 cur == nullptr时，循环结束。

此时pre指向的就是链表反转后的头节点。

算法实现

class Solution {
public:

    static ListNode * reverse(ListNode * head) {
        if(head == nullptr || head->next == nullptr) {return head;}
        ListNode * cur = head;
        ListNode * pre = nullptr;
        while (cur != nullptr) {
            ListNode * temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;

    }

    static ListNode * endOfFirstList(ListNode * head) {
        if(head == nullptr || head->next == nullptr) {return head;}
        ListNode * slow = head;
        ListNode * fast = head;
        while (fast->next != nullptr && fast->next->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;

    }

    static bool isPalindrome(ListNode* head) {
        if(head == nullptr || head->next == nullptr) {return true;}

        ListNode * endOfFirst = endOfFirstList(head);
        ListNode * startOfSecond = endOfFirst->next;
        endOfFirst->next = nullptr;
        startOfSecond = reverse(startOfSecond);

        ListNode * first = head, * second = startOfSecond;
        bool result = true;
        while (result && second != nullptr) {
            if(first->val != second->val) {
                result = false;
            }
            first = first->next;
            second = second->next;
        }
        startOfSecond = reverse(startOfSecond);
        endOfFirst->next = startOfSecond;
        return result;

    }


};

性能分析

时间复杂度：找到前半部分链表的尾结点和反转链表的时间复杂度都是$O(n)$，依次比较时间复杂度也是$O(n)$。所以总的时间复杂度是$O(n)$。

空间复杂度：$O(1)$。

官方做法

官方有三个做法，第一个就是我说的数组法。第三个和我的做法相同，反转链表法。

第二个是递归法。

下面只说递归法。

算法思想

因为单链表只能向后遍历，不能往回遍历。所以可以使用递归，一直递归到尾节点，然后回溯。递归方法外的定义一个变量，初始指向头节点。依次和回溯的进行比较。

算法实现

class Solution {
public:
    ListNode * front;

    bool recursion(ListNode * head) {
        if(head != nullptr) {
            if(!recursion(head->next)) {
                return false;
            }
            if(head->val != front->val) {
                return false;
            }
            front = front->next;
        }
        return true;

    }

    bool isPalindrome(ListNode* head) {
        front = head;
        return recursion(head);
    }
};

性能分析

时间复杂度：$O(n)$。

空间复杂度：在递归调用时，计算机会使用堆栈来存放调用前的数据。因此也是$O(n)$。