题目

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：
image.png

  1. 输入：head = [1,2,2,1]
  2. 输出：true

示例 2：
image.png

输入：head = [1,2]
输出：false

提示：

  • 链表中节点数目在范围[1, 10^5] 内

  • 0 <= Node.val <= 9


    进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

    解题方法

    翻转链表

    从链表的中间进行分割，将后半部分翻转，再遍历两段链表判定是否回文
    时间复杂度O(n)，空间复杂度O(1)。
    C++代码：

    /**
* 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;
      ListNode* fast = head;
      ListNode* pre = head;
      while(fast && fast->next) {
          pre = slow;
          slow = slow->next;
          fast = fast->next->next;
      }
      pre->next = nullptr;
      pre = nullptr;
      while(slow) {
          fast = slow->next;
          slow->next = pre;
          pre = slow;
          slow = fast;
      }
      ListNode* cur1 = head;
      ListNode* cur2 = pre;
      while(cur1 && cur2) {
          if(cur1->val != cur2->val)  return false;
          cur1 = cur1->next;
          cur2 = cur2->next;
      }
      return true;
  }
};

    递归回溯

    先通过递归到达最后一个节点，完成对比后将对比的节点指向下一个节点，通过回溯反向遍历。
    时间复杂度O(n)，空间复杂度O(n)。
    C++代码： ```cpp /**

    • 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 { private: ListNode pre;

public: bool backtracking(ListNode* cur) { if(cur) { if(!backtracking(cur->next)) return false; if(cur->val != pre->val) return false; pre = pre->next; } return true; }

bool isPalindrome(ListNode* head) {
    pre = head;
    return backtracking(head);
}

}; ```