LeetCode234.回文链表

更新: 1/31/2026 字数: 0 字 时长: 0 分钟

题目链接:

234. 回文链表 - 力扣（LeetCode）

题目大意就是给出一个链表，我们判断这个链表是否回文。

INFO

普通的判断回文只需要两个指针分别从前，后往中间走进行判断就可以了，这里的问题在于链表是单向的，我们要如何处理。

法一：转为数组

那么我们可以对这个链表进行遍历，将数的内容放到一个数组里面，然后再进行判断。这样的时间复杂度和空间复杂度都是。

法二：在原有链表上进行操作

既然我们需要从后往前遍历，那么是不是只要对原链表的后半部分进行反转就好了，这一步与LeetCode206.反转链表是一样的，然后我们再分别从前半部分和后半部分进行操作对比就好了。

这样的时间复杂度为,而空间复杂度只有。代码如下:

/**
 * 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 = head,*fast = head;
        while(fast -> next != nullptr && fast -> next -> next != nullptr) {
            fast = fast -> next -> next;
            slow = slow -> next;
        }
        // 反转链表
        ListNode *last = nullptr, *current = slow -> next;
        while(current != nullptr) {
            ListNode *tmp = current -> next;
            current -> next = last;
            last = current;
            current = tmp;
        }
        // 判断
        slow = head;
        while(last != nullptr && slow != nullptr) {
            if(slow -> val != last -> val)return false;
            slow = slow -> next,last = last -> next;
        }
        return true;
    }
};