LeetCode234_234. 回文链表

一、描述

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true

示例 2：

输入：head = [1,2]
输出：false

提示：

链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9

二、题解

方法一：利用栈的特性。给里面的值放到栈里面，然后在给依次取出来栈里面的元素和原有的链表的值比较。

    //方法一：利用栈的特性。给里面的值放到栈里面，然后在给依次取出来栈里面的元素和原有的链表的值比较。
    // 这是第一反应相到的方法。
    /*
    执行结果：通过
    执行用时：36 ms, 在所有 Java 提交中击败了75.86%的用户
    内存消耗：58.2 MB, 在所有 Java 提交中击败了22.73%的用户
    通过测试用例：90 / 90
     */
    public boolean isPalindrome(ListNode head) {
        Stack<Integer> stack = new Stack<Integer>();
        ListNode dummy = head;//注意定义一个虚拟头节点，防止原有链表结构改变。
        while (dummy != null) {
            stack.push(dummy.val);
            dummy = dummy.next;
        }
        while (head != null) {
            if (head.val == stack.pop()){
                head = head.next;//相等的话，元素依次往下比较。直到找到不同的元素返回false
            } else {
                return false;//直到找到不同的元素返回false
            }
        }
        return true;//没有发现栈和原有链表对应位置上的不同的元素，就代表是回文的，返回true。
    }

LeetCode 206. 反转链表
LeetCode 207. 课程表
LeetCode 208. 实现 Trie (前缀树)
LeetCode 209. 长度最小的子数组
LeetCode 210. 课程表 II
LeetCode 217. 存在重复元素
LeetCode 229. 多数元素 II
LeetCode 231. 2 的幂
LeetCode 234. 回文链表
LeetCode 237. 删除链表中的节点
LeetCode 242. 有效的字母异位词
LeetCode 257. 二叉树的所有路径

声明：
        题目版权为原作者所有。文章中代码及相关语句为自己根据相应理解编写，文章中出现的相关图片为自己实践中的截图和相关技术对应的图片，若有相关异议，请联系删除。感谢。转载请注明出处，感谢。

By luoyepiaoxue2014

B站： https://space.bilibili.com/1523287361 点击打开链接
微博： http://weibo.com/luoyepiaoxue2014 点击打开链接