回文链表(java代码).docx
需积分: 5 105 浏览量
2024-03-21
09:25:35
上传
评论
收藏 9KB DOCX 举报
要判断一个链表是否回文，可以先找到链表的中间节点，然后将后半部分链表反转，最后分
别从链表头和反转后的链表头开始比较节点的值是否相等。
具体的步骤如下：
1. 如果链表为空或仅含一个节点，则直接返回 true。
2. 使用快慢指针找到链表的中间节点。快指针每次移动两步，慢指针每次移动一步，当快
指针到达链表尾部时，慢指针正好处于链表的中间位置。
3. 反转链表的后半部分。从慢指针处开始，将链表后半部分的节点反转。
4. 比较链表的前半部分和反转后的后半部分。从链表头和反转后的链表头开始同时遍历两
个链表，比较节点的值是否相等，如果有不相等的节点，则返回 false；如果遍历完毕都没
有不相等的节点，则返回 true。
Java 代码实现如下：
```java
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
// 找到链表的中间节点
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 反转链表的后半部分
ListNode prev = null;
ListNode curr = slow.next;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
// 比较链表的前半部分和反转后的后半部分
ListNode p1 = head;
ListNode p2 = prev;
while (p1 != null && p2 != null) {
资源评论
