给你一个单链表的头节点 head ，请你判断该链表是否为
回文链表
。如果是，返回 true ；否则，返回 false 。
示例 1：
1 -> 2 -> 2 -> 1 -> null
输入：head = [1,2,2,1]
输出：true
示例 2：
1 -> 2 -> null
输入：head = [1,2]
输出：false
提示：
- 链表中节点数目在范围
[1, 105]内 - $0 <= Node.val <= 9$
进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
分析
- 利用数组存储链表节点，进行回文遍历比对
- 求链表长度，利用栈，存储前半部分，然后出栈依次和后半部分比较，不一致，则返回false
- 递归，维护一个全局变量，引用前一个节点
利用数组存储链表节点，进行回文遍历比对
class Solution {
public boolean isPalindrome(ListNode head) {
List<Integer> vals = new ArrayList<Integer>();
// 将链表的值复制到数组中
ListNode currentNode = head;
while (currentNode != null) {
vals.add(currentNode.val);
currentNode = currentNode.next;
}
// 使用双指针判断是否回文
int front = 0;
int back = vals.size() - 1;
while (front < back) {
if (!vals.get(front).equals(vals.get(back))) {
return false;
}
front++;
back--;
}
return true;
}
}
递归方法
- currentNode 非空节点，先递归尾部
- 不是回文直接返回false
- 头尾依次对比
- 不是回文直接返回false
- 更新节点frontPointer，ps: currentNode 递归更新
- 返回true
class Solution {
private ListNode frontPointer;
private boolean recursivelyCheck(ListNode currentNode) {
if (currentNode != null) {
// 先递归尾部
if (!recursivelyCheck(currentNode.next)) {
return false;
}
// 头尾依次对比
if (currentNode.val != frontPointer.val) {
return false;
}
// 更新头，因为尾部递归了
frontPointer = frontPointer.next;
}
return true;
}
public boolean isPalindrome(ListNode head) {
frontPointer = head;// 记录frontPointer
return recursivelyCheck(head);
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
