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

方法一：使用双指针、反转链表求解（推荐）

如果一个链表为回文结构，则链表的前半段和后半段是对称的。

1、利用两个指针（快指针、慢指针），快指针每次移动两个结点，慢指针每次移动一个结点，可以得到链表的中间结点；

2、得到链表的中间结点，从中间结点开始将后续的链表进行反转；

3、比较链表前半段和后半段的值是否对称。

时间复杂度：o(n)

空间复杂度：o(1)

class Solution {
  public:
    //反转链表
    ListNode* reverse(ListNode* phead) {
        ListNode* ptemp = nullptr;
        while (phead) {
            ListNode* pnext = phead->next;
            phead->next = ptemp;
            ptemp = phead;
            phead = pnext;
        }
        return ptemp;
    }

    bool isPail(ListNode* head) {
        //特殊情况处理
        if (head == nullptr || head->next == nullptr)
            return true;

        ListNode* slow = head;
        ListNode* fast = head;
        //得到链表的中点
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        //从链表中点开始反转链表
        ListNode* pend = reverse(slow);
        //前半段链表和后半段链表进行对比是否对称
        while (pend != nullptr) {
            if (pend->val != head->val)
                return false;
            pend = pend->next;
            head = head->next;
        }
        return true;
    }
};

方法二：利用栈求解

利用栈先进后出的特点将链表存进栈中，再对比链表和栈的值即可判断是否为回文结构

时间复杂度：o(n)

空间复杂度：o(n)

class Solution {
public:
    bool isPail(ListNode* head) {
        //特殊情况处理
        if (head == nullptr || head->next == nullptr)
            return true;

        stack<ListNode*> sk;
        ListNode* ptemp = head;
        while (ptemp) {
            sk.push(ptemp);
            ptemp = ptemp->next;
        }

        while (head) {
            if((head->val) != (sk.top()->val))
                return false;
            head = head->next;
            sk.pop();
        }
        return true;
    }
};