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

发表于 更新于 分类于 ， ， ， ， 阅读次数： 阅读次数： 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 出来跟链表从头开始比较，全对上了就是回文了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * 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;
    }
}