一、题目：
给你一个单链表的头节点 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) 空间复杂度解决此题？
二、实现算法
1、存入数组，然后双指针法判断
public boolean isPalindrome(ListNode head) {
List<Integer> list = new ArrayList<>();
ListNode currentNode = head;
while(currentNode != null) {
list.add(currentNode.val);
currentNode = currentNode.next;
}
int left = 0;
int right = list.size() - 1;
while (left < right) {
if (!list.get(left).equals(list.get(right))) {
return false;
}
left++;
right--;
}
return true;
}
2、快慢指针一（反转后半链表）
public boolean isPalindrome(ListNode head) {
if (head == null) {
return true;
}
ListNode slow = head,fast = head;
// 首先找到前半部分的尾结点
while(fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
slow = slow.next;
// 然后反转后半部分链表
ListNode pre = null;
while(slow != null) {
ListNode temp = slow.next;
slow.next = pre;
pre = slow;
slow = temp;
}
// 判断是否回文
while (head != null && pre != null) {
if (head.val != pre.val) {
return false;
}
head = head.next;
pre = pre.next;
}
return true;
}
3、快慢指针二（反转前半链表）
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
ListNode slow = head, fast = head;
ListNode pre = null;
while(fast != null && fast.next != null) {
fast = fast.next.next;
ListNode temp = slow.next;
slow.next = pre;
pre = slow;
slow = temp;
}
if (fast != null) {
slow = slow.next;
}
while(pre != null && slow != null) {
if (pre.val != slow.val) {
return false;
}
pre = pre.next;
slow = slow.next;
}
return true;
}
三、算法图解分析
以快慢指针二为例进行图解分析：
1、初始化
ListNode slow = head,fast = head；
ListNode pre = null;
2、第一轮循环
fast= fast.next.next;
ListNode temp = slow.next;
slow.next = pre;
pre = slow;
slow = temp;
3、第二轮循环
fast= fast.next.next;
ListNode temp = slow.next;
slow.next = pre;
pre = slow;
slow = temp;
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/122974.html
