✨专栏:《Java SE语法》 | 《数据结构与算法》 | 《C生万物》
❤️感谢大家点赞👍🏻收藏⭐评论✍🏻,您的三连就是我持续更新的动力❤️
🙏小杨水平有限,欢迎各位大佬指点,相互学习进步!
1. 题目描述
对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。
给定一个链表的头指针A,请返回一个bool
值,代表其是否为回文结构。保证链表长度小于等于900。
测试样例:
2. 思路
-
判断链表是否为空,如果为空,那么链表就是回文的
-
找到中间元素
- 定义两个指针
slow
和fast
,fast
每次移动两步,slow
每次移动一步,当fast
走到链表中的最后一个节点是,slow
就指向了链表的中间节点。
- 定义两个指针
-
反转链表后半部分的元素
- 定义指针
cur
指向中间节点的next
- 从中间节点循环遍历链表
- 定义指针
curNext
指向cur
的next
(保存下一个节点) - 将当前节点的
next
指向slow
slow
移动到当前节点的cur
位置cur
移动到下一个节点
- 定义指针
-
同时遍历反转后的链表和原始链表的前半部分,并比较每个节点的值。如果所有的节点都匹配,那么链表就是回文;否则它不是回文。
- 一个从前一个从后循环遍历链表,直到相遇
- 判断两个当前节点是否相同,如果不同返回
false
- 如果相同判断
head
的next
等不等于slow
,如果等于直接返回true
(链表节点个数为偶数个) head
移动到下一个节点slow
移动到下一个节点
3. 代码
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class PalindromeList {
public boolean chkPalindrome(ListNode head) {
if (head == null) {
return true;
}
// write code here
// 1.找到中间元素
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
// 2.反转链表
ListNode cur = slow.next;
while (cur != null) {
ListNode curNext = cur.next;
cur.next = slow;
slow = cur;
cur = curNext;
}
// 3.一个向后遍历一个向前遍历
while (slow != head) {
if (slow.val != head.val) {
return false;
}
if (head.next == slow) {
return true;
}
head = head.next;
slow = slow.next;
}
return true;
}
}
运行结果: