LeetCode 234 回文链表：三种解法对比与实现

今天这道题是 LeetCode 234 回文链表，题目很简单：给你一个单链表的头节点 head，请你判断该链表是否为回文链表（回文序列是向前和向后读都相同的序列）。如果是，返回 true；否则，返回 false。

方法一：数组缓存法

最开始看到这道题，我脑子里冒出来的想法是：用两个指针，一个在头，一个在尾，然后往中间移动，逐一比较。但问题是，这是个单链表，没法直接拿到尾节点的前驱，这个思路在单链表里走不通。

那怎么办？既然链表不方便，那就把它变成我熟悉的结构。

• 先遍历一遍链表，统计总共有多少个节点，确定数组的长度。
• 再遍历一遍链表，把每个节点的 val 存到数组里。
• 最后用双指针法在数组上判断回文，这个就很顺手了。

代码

class Solution {
 public:
  bool isPalindrome(ListNode* head) {
   if (head->next == nullptr) {
    return true;
   }
   ListNode* p = head;
   int len = 0;
   while (p != nullptr) {
    len++;
    p = p->next;
   }
   vector<int> arr(len);
   p = head;
   for (int i = 0; i < len && p != nullptr; i++) {
    arr[i] = p->val;
    p = p->next;
   }
   int left = 0, right = len - 1;
   while (left < right) {
    if (arr[left] != arr[right]) {
     return false;
    }
    left++;
    right--;
   }
   return true;
  }
};

复杂度分析

n 为链表的结点数

时间复杂度：O(n)。三次遍历，统计长度、填充数组、双指针对比，整体是线性的。

空间复杂度：O(n)。数组申请的空间为 n。用了一个和链表等长的数组，这是个明显的短板。

这个方法胜在思路直接、代码好写、不容易出错，但空间开销有点大。我就在想，能不能不用额外的数组？于是去看了官方题解。

方法二：快慢指针 + 反转链表

要想让空间复杂度为 O(1)，就不能用额外的存储空间，只能在链表本身上做文章。