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

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <algorithm>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    bool isPail(ListNode* head) {
        // write code here 
        //copy the head
        ListNode* headd_head = head;
        ListNode* node = new ListNode(head->val);
        ListNode* node_copy = node;
        while (head) {
            if (head->next==nullptr) {
                break;
            }
            head = head->next;
            node->next = new ListNode(head->val);
            node = node ->next;
        }
        head = headd_head;

        ListNode* headreverse = reverseList(node_copy);

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

    ListNode* reverseList(ListNode* headd){
        ListNode* newhead = nullptr;
        while (headd!=NULL) {
            ListNode* tmp = headd->next;
            headd->next = newhead;
            newhead = headd;
            headd = tmp;
        }
        return newhead;
    }
};

自己的思路：

把原始链表反转，和反转前的链表做对比，如果一致，则是回文

时间复杂度O（N），空间复杂度因为new了一个新的node链表，作为head的备份，所以是O（N）

关键点1：copy一个head的备份链表，因为reverse操作会把head的头节点改变

关键点2：反转链表

关键点3：反转后的链表与链表做对比，不能直接==判断，因为链表内部还包含地址变量，数值一致，地址不一致，也会是不相等。因此，需要循环对比内部节点的数值。

over！