234. 回文链表

二刷

class Solution {
public:
  bool isPalindrome(ListNode* head) {
    vector<int> V;
    while (head) {
      V.push_back(head->val);
      head = head->next;
    }
    int L = 0, R = V.size() - 1;
    while (L < R)
      if (V[L++] != V[R--])
        return false;
    return true;
  }
};

我去啊，我用栈辅助、边走边对的思路竟然是行不通的，因为在线的栈匹配算法会接受任何类似 122331 的串，所以事实上最好的方案仍然是递归，或者数组辅助双指针。

但是这个题如果真用递归做的话其实也非常优雅，用到的就是递归逆序返回的原理，实际上类似于双指针，这个解法是非常清晰易懂的。

class Solution {
  ListNode *LTR{};
  bool Recurse(ListNode *Head) {
    if (Head == nullptr) {
      return true;
    } else {
      bool Ret = Recurse(Head->next);
      int LTRVal = LTR->val;
      LTR = LTR->next;
      return LTRVal == Head->val && Ret;
    }
  }
public:
  bool isPalindrome(ListNode* head) {
    LTR = head;
    return Recurse(head);
  }
};

三刷

class Solution {
  ListNode *Reverse(ListNode *head) {
    ListNode *Prev = nullptr;
    ListNode *Cur = head;
    while (Cur) {
      ListNode *Next = Cur->next;
      Cur->next = Prev;
      Prev = Cur;
      Cur = Next;
    }
    return Prev;
  }
public:
  bool isPalindrome(ListNode* head) {
    ListNode *Slow = head, *Fast = head;
    while (Fast && Fast->next) {
      Slow = Slow->next;
      Fast = Fast->next->next;
    }
    // Count of the list is an odd number.
    if (Fast && !Fast->next)
      Slow = Slow->next;

    Slow = Reverse(Slow);

    while (Slow) {
      if (head->val != Slow->val)
        return false;
      head = head->next;
      Slow = Slow->next;
    }
    return true;
  }
};

我操，我猜对了，\(\mathrm O(1)\) 空间竟然真是这么写的。