234-回文链表

LeetCode 234. Palindrome Linked List

LeetCode-234

Given the head of a singly linked list, return true if it is a palindrome.

Example 1:

Input: head = [1,2,2,1]
Output: true

method 1: 模拟

反转后半段链表，头尾指针从两边向中间比较

ListNode* reverseList(ListNode *head) {
    if (!head || !head->next) return head;
    ListNode *newHead = reverseList(head->next);
    head->next->next = head;
    head->next = NULL;
    return newHead;
}

bool isPalindrome(ListNode* head) {
    ListNode *slow = head;
    ListNode *fast = head;
    while(fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    ListNode *tail = reverseList(slow);
    while (head && tail) {
        if (head->val != tail->val) return false;
        head = head->next;
        tail = tail->next;
    }
    return true;
}

时间复杂度：$O(n)$
空间复杂度：$O(1)$

method 2: 递归

如果要求不能修改链表，只能用递归
因为递归总是先从最后一个元素开始处理的，相当于有个指针从后往前走
所以用一个全局的指针从前往后走就可以相互比较了

利用栈先进后出的特性从后往前遍历

ListNode *front = nullptr;
bool traversal(ListNode *cur) {
    if (!cur) return true;
    if (!traversal(cur->next)) return false;    // 先去处理下一个节点，如果下一个节点不行，就直接返回
    if (cur->val != front->val) return false;   // 如果当前节点不行，也直接返回
    front = front->next;    // 当前节点可以的话front往后移
    return true;    // 前面的条件都过了，说明到此为止是回文
}
bool isPalindrome(ListNode* head) {
    ListNode *fast = head;
    ListNode *slow = head;
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
    }   // 增加了寻找中间节点，可以不用
    front = head;
    return traversal(slow);
}

先找到中间节点，从中间节点开始递归

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