234. 回文链表
分析
-
计算链表长度
- 遍历链表一次,统计节点总数
len
。用于确定需要存入栈的节点数量
- 遍历链表一次,统计节点总数
-
存储前半部分元素到栈中
- 再次遍历链表,将前半部分的节点值压入栈中。如果链表长度为奇数,则跳过中间节点(因为中间节点不影响回文判断)
-
比较后半部分的值
- 从链表中间位置开始继续遍历链表,每遇到一个节点,就弹出栈顶的元素,与当前节点值比较。如果有任意不相等的情况,说明链表不是回文链表
-
判断结果
- 遍历完后,若所有值都匹配,则链表是回文的,返回
true
- 遍历完后,若所有值都匹配,则链表是回文的,返回
时间复杂度
时间复杂度 O(n)
空间复杂度
空间复杂度为 O(n)
C++代码
|
|