力扣: 回文链表

2024/10/25 21:32:46 来源：https://blog.csdn.net/Snowyyds/article/details/141848224 浏览: 次关键词：力扣: 回文链表

文章目录

需求
分析
优化下
结尾

在这里插入图片描述

需求

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

示例 1：
在这里插入图片描述

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

示例 2：
在这里插入图片描述

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

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

进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

分析

题意还是挺简单的, 我们可以先把链表遍历一遍, 将链表里的数据存到一个容器里面, 再拿容器里的数据和链表比较就行了, 想这里 , 栈是再合适不过了, 我说的是数据结构里的栈, 注意不是下图里的 zhan 啊.

在这里插入图片描述

思路到了这里, 其实代码也就跃然纸上了:

public boolean isPalindrome(ListNode head) {//  全部放到栈里ListNode temp = head;Stack<Integer> stack = new Stack<>();while( temp != null ){stack.push(temp.val);temp = temp.next;}temp = head;while( temp != null ){if( temp.val != stack.pop() ){return false;}temp = temp.next;}return true;
}

代码解释:

首先，定义一个 temp 变量指向链表的头节点 head。
创建一个 Stack 类型的栈 stack，用于存储链表节点的值。
使用 while 循环遍历整个链表，将每个节点的值 temp.val 压入栈中，然后将 temp 移动到下一个节点 temp.next。遍历完成后，栈中保存了链表节点值的逆序。

重新将 temp 指向链表的头节点。
再次使用 while 循环遍历链表：
对于每个节点，弹出栈顶的值，并与当前节点的值进行比较。
如果当前节点的值与弹出的栈顶值不相等，则说明链表不是回文链表，返回 false。
否则，继续遍历下一个节点。
如果所有节点的值与栈中的值都匹配，则说明链表是回文链表，返回 true。

执行结果:

在这里插入图片描述

优化下

上面的解答解决了, 但是有些点事可以优化的, 在比较的过程中其实没有必要全部比较啊, 我们只需要拿前一半和后一半比较就行了 , 那么问题的关键就是拿到链表的长度, 然后再拿到中间节点就行了.

public boolean isPalindrome(ListNode head) {//  全部放到栈里ListNode temp = head;Stack<Integer> stack = new Stack<>();int l = 0;while( temp != null ){stack.push(temp.val);temp = temp.next;l++;}temp = head;l = l / 2;while( l > 0 ){if( temp.val != stack.pop() ){return false;}temp = temp.next;l--;}return true;
}