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

判断一个链表是否为回文结构
题意:
给定一个链表，请判断该链表是否为回文结构。

输出描述:
如果给定的链表是回文结构则输出true否则false

案例
输入：[1,2,2,1]
返回值：true
说明：1->2->2->1

方法一: 栈

因为回文的性质,所以可以考虑使用栈，将所有链表压入栈中,因为栈的性质所以链表中最尾部的位置将在栈顶,所以每次将栈弹出元素进行判断即可.
图片说明

ListNode *st[1000010];    //使用st数组来模拟栈
    bool isPail(ListNode* head) {
        // write code here
        ListNode *heads = head;  
        int tot = 0;
        while(heads){    //将链表所有元素押入栈中
            st[++ tot] = heads;
            heads = heads->next;
        }
        while(tot){    //从栈尾向前判断
            if(head->val != st[tot]->val) return false; //如果当前值不同说明该链表不是回文
            head = head->next;
            tot --;
        }
        return true;   
    }

时间复杂度: $O(n)$ 遍历两次链表总体复杂度为 $O(n)$
空间复杂度: $O(n)$ 栈存储整个链表元素

方法二: 递归

因为回文的性质,从前往后和从后往前遍历的值一样，所以先递归到链表的尾结点,之后从后往前判断每一位置是否相等.

ListNode *heads;
    bool fase;
    bool isPail(ListNode* head) {
        // write code here
        heads = head;
        return just(head);
    }
    bool just(ListNode *now){//递归函数
        if(!now->next){//到达链表尾部
            fase = heads->val == now->val;//判断值是否与对应位置相等
            heads = heads->next;
            return fase;
        }else{
            fase =just(now->next);
            if(!fase) return false;//如果前面出现不相等情况直接全部为false
            fase = heads->val == now->val;//判断值是否与对应位置相等
            heads = heads->next;
            return fase;
        }
    }

时间复杂度: $O(n)$ 递归次数相当于链表的长度
空间复杂度: $O(n)$ 递归中会产生的空间相当于链表的长度