题解 | #判断一个链表是否为回文结构#

• 反转链表的方式：

struct ListNode {
  int val;
  struct ListNode *next;
  explicit ListNode(int v) : val(v) , next(nullptr) {}
};

ListNode* reverseList(ListNode* head) {
  if (head == nullptr) return head;
  ListNode* p = nullptr;
  ListNode* q = head;
  ListNode* r = nullptr;
  while (q) {
    r = q->next;
    q->next = p;
    p = q;
    q = r;
  }
  return p;
}

bool isPail(ListNode* head) {
  if (head == nullptr || head->next == nullptr) return true;
  ListNode* slow = head;
  ListNode* fast = head;
  while (fast && fast->next) {
    fast = fast->next->next;
    slow = slow->next;
  }
  auto head2 = slow->next;
  slow->next = nullptr;
  auto new_head = reverseList(head2);
  head2->next = slow;
  while (head && new_head) {
    if (head->val != new_head->val) return false;
    head = head->next;
    new_head = new_head->next;
  }
  return true;
}

ListNode* CreateList(vector<int>& vec) {
  auto dummy = new ListNode(0);
  auto p = dummy;
  for (auto v : vec) {
    auto node = new ListNode(v);
    p->next = node;
    p = p->next;
  }
  return dummy->next;
}

int main() {
  vector<int> vec{ 1,2,3,2,1 };
  auto head = CreateList(vec);
  auto ans = isPail(head);
  return 0;
}

• 使用栈的方式:

    bool isPail(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return true;
        stack<ListNode*> st;
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast && fast->next) {
            fast = fast->next->next;
            st.emplace(slow);
            slow = slow->next;
        }
        if(fast) st.emplace(slow);    // 奇数个
        while(!st.empty() && slow) {
            auto cur = st.top();
            st.pop();
            if(cur->val != slow->val) return false;
            slow=slow->next;
        }
        return st.empty();
    }