面试题 02.06. 回文链表
题目
编写一个函数,检查输入的链表是否是回文的。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶:
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?
题解
public boolean isPalindrome(ListNode head) {
int count = 0;
ListNode node = head;
// 计算节点数量
while (node != null) {
count++;
node = node.next;
}
node = head;
int mid = count / 2, cursor = 0;
int[] left = new int[mid];
// 缓存左边半段链表数值 指针移动到中间节点
while (cursor < mid) {
left[cursor++] = node.val;
node = node.next;
}
// 若是奇数节点数 跳过中间节点判断
if (count % 2 == 1) {
node = node.next;
}
// 判断后半段链表和缓存数据的倒叙比较
cursor = 0;
while (cursor++ < mid) {
if (left[mid - cursor] != node.val) {
return false;
}
node = node.next;
}
return true;
}