# Nicksxs's Blog

What hurts more, the pain of hard work or the pain of regret?

0%

# Leetcode 234 回文链表(Palindrome Linked List) 题解分析

Posted on 2020-11-15 In Java , leetcode , Linked List , java , Linked List Views: Views: Disqus:

## 题目介绍

Given a singly linked list, determine if it is a palindrome.
给定一个单向链表，判断是否是回文链表

### 例一 Example 1:

Input: 1->2
Output: false

### 例二 Example 2:

Input: 1->2->2->1
Output: true

### 挑战下自己

Follow up:
Could you do it in O(n) time and O(1) space?

## 简要分析

首先这是个单向链表，如果是双向的就可以一个从头到尾，一个从尾到头，显然那样就没啥意思了，然后想过要不找到中点，然后用一个栈，把前一半塞进栈里，但是这种其实也比较麻烦，比如长度是奇偶数，然后如何找到中点，这倒是可以借助于双指针，还是比较麻烦，再想一想，回文链表，就跟最开始的一样，链表只有单向的，我用个栈不就可以逆向了么，先把链表整个塞进栈里，然后在一个个 pop 出来跟链表从头开始比较，全对上了就是回文了

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public boolean isPalindrome(ListNode head) {
            if (head == null) {
                return true;
            }
            ListNode tail = head;
            LinkedList<Integer> stack = new LinkedList<>();
            // 这里就是一个循环，将所有元素依次压入栈
            while (tail != null) {
                stack.push(tail.val);
                tail = tail.next;
            }
            // 在逐个 pop 出来，其实这个出来的顺序就等于链表从尾到头遍历，同时跟链表从头到尾遍历进行逐对对比
            while (!stack.isEmpty()) {
                if (stack.peekFirst() == head.val) {
                    stack.pollFirst();
                    head = head.next;
                } else {
                    return false;
                }
            }
            return true;
        }
    }

Related Posts

- Leetcode 160 相交链表(intersection-of-two-linked-lists) 题解分析
- Leetcode 48 旋转图像(Rotate Image) 题解分析
- Leetcode 105 从前序与中序遍历序列构造二叉树(Construct Binary Tree from Preorder and Inorder Traversal) 题解分析
- Leetcode 121 买卖股票的最佳时机(Best Time to Buy and Sell Stock) 题解分析
- Leetcode 124 二叉树中的最大路径和(Binary Tree Maximum Path Sum) 题解分析