描述

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

示例1

输入：
[1]

返回值：
true

示例2

输入：
[2,1]

返回值：
false

说明：2->1

示例3

输入：
[1,2,2,1]

返回值：
true

说明：1->2->2->1 

思路:

可以将链表上的节点放入一个队列中，然后每次弹出队列头以及队列尾的元素，比较 -> 如果两个都不为空，并且值不相等则为非回文链表；否则继续弹出队头队尾元素。

AC 代码

public boolean isPail (ListNode head) {
        // write code here
        if (head == null) {
            return false;
        }
        LinkedList<ListNode> queue = new LinkedList<>();
        // 元素入队
        while (head != null) {
            queue.offer(head);
            head = head.next;
        }
        // 当元素不为空并且存在两个及两个以上元素时
        // 之所以是两个，是因为一个元素本身就是回文的
        while (!queue.isEmpty() && queue.size() > 1) {
            // 弹出队头元素
            ListNode first = queue.removeFirst();
            // 弹出队尾元素
            ListNode last = queue.removeLast();
            // 如果不相等，则为非回文链表
            if (first != null && last != null && first.val != last.val) {
                return false;
            }
        }
        return true;
    }

• 时间复杂度：O(n),n 为链表长度，需要遍历一遍链表
• 空间复杂度：O(n)，需要大小为 n 的队列

  最后

  大家可以去 【牛客网-题库-在线编程】去练习一下。
  可以去微信搜索：【蘑菇睡不着】交个朋友～
  也可以扫描下方二维码。