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

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */

class Solution {
  public:
    /**
     *
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    bool isPail(ListNode* head) {
        // write code here
	  //要用一个新的链表去存储head的节点值，否则反转之后head会变
        int len = getLength(head);
        ListNode* newHead = new ListNode(0);
        ListNode* cur = newHead;
        ListNode* tmp = head;
        for(int i = 0; i < len; i++){
            newHead->next = new ListNode(tmp->val);
            tmp = tmp->next;
            newHead = newHead->next;
        }
        cur = cur->next;
        ListNode* list = reserve(head);
        for (int i = 0; i < len; i++) {
            if (list->val != cur->val) return false;
            list = list->next;
            cur = cur->next;
        }
        return true;
    }
    ListNode* reserve(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        ListNode* tmp = nullptr;
        while (cur != nullptr) {
            tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
    int getLength(ListNode* head) {
        int len = 0;
        while (head != nullptr) {
            head = head->next;
            len++;
        }
        return len;
    }
};