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

题意整理：
给定一个链表，判断其是否是回文结构，即其是否是中心对称的。
解法一：
思路：
看到题目后，想到了学习python时的一个小作业，就是判断一个字符串是否回文。所以这道题可以先将链表转化为列表：
图解：
图片说明

将链表转化为列表后，直接用"=="判断列表与它的逆序列表是否相等，即可判断出原链表是否回文。若逆序列表与原列表相等，即是回文的；若不相等，即不是回文的。

代码：

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

#
# 
# @param head ListNode类 the head
# @return bool布尔型
#
class Solution:
    def isPail(self , head ):
        # write code here
        cur=head
        ans=[]//用来存放链表节点值的列表
        while cur:
            ans.append(cur.val)
            cur=cur.next//循环将各个节点的值保存到列表中

        a = (ans == ans[::-1])//判断逆序列表与原列表是否相等，并将值保存在a中

        return a

复杂度分析：
1、时间复杂度：由于复杂度最高的地方就是中间的循环体，为 $O(n)$ ，故该算法的时间复杂度为 $O(n)$ ；
2、空间复杂度：列表的空间复杂度为列表的长度，故该算法空间复杂度为 $O(n)$ 。

解法二：
思路：
由于题目是单链表，只能从前往后遍历，这里不考虑双指针的解法。
利用数据结构栈先进后出，后进先出的特性，将链表各节点的值保存在栈中。这样直接将链表的值与从栈取出的元素的值进行比较，就是将原链表与其逆序进行比较，只要出现不一样的值，即可返回false。
图解：
图片说明
代码：

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

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    bool isPail(ListNode* head) {
        // write code here
        stack <int>stk;//定义一个栈
        ListNode *cur = head;//定义一个临时指针来记录当前节点位置
        while(cur){
            stk.push(cur->val);
            cur=cur->next;//将链表各节点的值按从前往后的顺序，存在栈中
        }
        while(head){
            if(head->val != stk.top()){//由于c++中stack.pop()函数返回值是void型，故这里直接用栈顶元素
                return false;
            }
            stk.pop();//由于我们一直是用栈顶元素进行比较，故每次比较完，需要将栈顶元素pop出来
            head = head->next;
        }
        return true;
    }
};

复杂度分析：
1、时间复杂度：由于代码中是并列的两个循环，故时间复杂度是 $O(n)$ ；
2、空间复杂度：不管是顺序栈还是链式栈，我们存储数据只需要一个大小为 $n$ 的数组就够了。在入栈和出栈过程中，只需要一两个临时变量存储空间，所以空间复杂度是 $O(1)$ 。