您现在的位置是：首页 >学无止境 >力扣第234题 回文链表题解网站首页学无止境

力扣第234题 回文链表题解

题目描述

思路

给两个指针一个从初始位置向后移动，另一个在末尾位置向前移动，去比较每个元素值是否相等。

暴力解法

直接定义一个数组去记录每个元素的值，将链表问题转化为数组问题。代码如下

class Solution {
public:
    bool isPalindrome(ListNode *head) {
        ListNode *p = head;
        //记录链表长度
        int len = 0;
        while (head != nullptr) {
            len++;
            head = head->next;
        }
        int *arr = new int[len];
        for (int i = 0; i < len; ++i) {
            arr[i] = p->val;
            p = p->next;
        }
        int l = 0, r = len - 1;
        while (l <= r) {
            if (arr[l] != arr[r]) {
                return false;
            }
            l++,r--;
        }
        return true;
    }
};

这样利用了辅助空间，空间复杂度为O(n)。

优化

类似的思路还可以使用栈或者哈希来解决，但是这样优化不了空间复杂度，比如定义stack，将每个元素入栈后，再重新遍历链表，去与栈顶元素相比较。代码如下

class Solution {
public:
    bool isPalindrome(ListNode *head) {
        stack<int> s;
        ListNode *p = head;
        //遍历链表并入栈
        while (p) {
            s.push(p->val);
            p = p->next;
        }
        p = head; //重置节点位置
        while (head && head->val == s.top()) //判断节点是否为空，并且是否和栈顶相同
        {
            head = head->next;
            s.pop();  //判断完就出栈
        }
        if (s.size() > 0) { return false; } //栈不为空则返回false
        return true;
    }
};

利用栈的思路本质上还是数组的比较，并不能优化空间。

进阶思路

因为回文链表的前半段与后半段刚好是反转的关系，所以可以考虑将后半部分链表逆置，再与前半部分链表逐一比较。代码如下

class Solution {
    //找到链表的中间结点
    ListNode* midNode(ListNode* head) {
        ListNode* slow = head, *fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

    //反转链表
    ListNode *reverseList(ListNode *head) {
        if (head == nullptr) {
            return head;
        }
        ListNode *pre = new ListNode();
        pre->next = nullptr;
        ListNode *p = head;
        while (p != nullptr) {
            ListNode *q = p->next;
            p->next = pre->next;
            pre->next = p;
            p = q;
        }
        head = pre->next;
        return head;
    }

public:
    bool isPalindrome(ListNode* head) {
        ListNode* mid = midNode(head);
        ListNode* head2 = reverseList(mid);
        while (head2) {
            if (head->val != head2->val) {
                return false;
            }
            head = head->next;
            head2 = head2->next;
        }
        return true;
    }
};

原地逆置链表的空间复杂度为O(1)，优化了空间。