Version: Next
234.回文链表
难度 简单
请判断一个链表是否为回文链表。
Given the head of a singly linked list, return true if it is a palindrome.
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶：
- 你能否用 O(n) 时间复杂度和
O(1) 空间复杂度解决此题？ - 如果要求不能破坏原链表的结构
队列 + 栈
- 空间复杂度不够低
- 遍历链表，每个节点都加入一个
队列和一个栈（用双端队列实现）- 全部添加完毕后，队列出队，栈出栈，同步比较，全部相等则为回文链表
public static boolean isPalindrome(ListNode head) {
if (head.next == null) return true;
if (head.next.next == null) return head.val == head.next.val;
Queue<ListNode> queue = new LinkedList<>();
Deque<ListNode> deque = new LinkedBlockingDeque<>();
while (head != null) {
queue.add(head);
deque.add(head);
head = head.next;
}
while (queue.size() != 0) {
ListNode l1 = queue.remove();
ListNode l2 = deque.removeLast();
if (l1.val != l2.val) return false;
}
return true;
}
快慢指针法
找中央节点
- 中央节点：如果某节点的 next 节点，是回文链表右侧部分的起始节点，则称其为
中央节点- 通过在 LeetCode 网页输入空测试用例，发现现在这道题至少存在一个节点，所以不用判断空
- 如果链表只有一个节点，返回 true
- 如果链表只有两个节点，那么他们值必须相等
- 链表有3个及以上节点，利用
快慢指针法，找到中央节点
- 快慢指针都指向头节点
- 慢指针一次走一步，快指针一次走两步
- 当
快指针.next.next = null时，链表一定有偶数个元素，此时慢指针就指着中央节点- 当
快指针.next = null是，链表一定有奇数个元素，此时慢指针指着中央节点- 将右侧
(中央节点, null)之间的的部分链表进行翻转- 两侧一起遍历，比较
值是否相等，直到右链表达到 null 时，之前对比结果全部相等，则返回 ture- 否则 false
public static boolean isPalindrome1(ListNode head) {
if (head.next == null) return true;
if (head.next.next == null) return head.val == head.next.val;
// 获得中心节点
ListNode middleNode = getMiddleNode(head);
// 反转右侧链表
ListNode rightHead = reverse(middleNode);
while (rightHead != null) {
if (head.val != rightHead.val) return false;
head = head.next;
rightHead = rightHead.next;
}
return true;
}
private static ListNode getMiddleNode(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (true) {
if (fast.next != null) {
if (fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
} else {
return slow;
}
} else {
return slow;
}
}
}
private static ListNode reverse(ListNode middle) {
ListNode pre = null;
ListNode next = middle.next;
ListNode originalNext;
while (next != null) {
originalNext = next.next;
next.next = pre;
pre = next;
next = originalNext;
}
return pre;
}