LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 从中点拆分为两个链表，翻转一个再与另一个对比即可

class Solution {
 public:
  bool isPalindrome(ListNode* head) {
    if (!head || !head->next) {
      return true;
    }
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) {
      slow = slow->next;
      fast = fast->next->next;
    }  // slow现在为中点，拆分出以slow为头节点的链表
    ListNode* pre = nullptr;
    while (slow) {  // 翻转拆分出的链表
      ListNode* t = slow->next;
      slow->next = pre;
      pre = slow;
      slow = t;
    }  // pre为翻转后的链表头节点
    ListNode* cur = head;
    while (pre) {  // 对比两个链表
      if (cur->val != pre->val) {
        return false;
      }
      cur = cur->next;
      pre = pre->next;
    }
    return true;
  }
};