Nicksxs's Blog

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

0%

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

题目介绍

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;
}
}
请我喝杯咖啡