回文链表java实现
时间: 2023-07-10 09:17:51 浏览: 53
以下是一个 Java 实现:
```java
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
// 找到链表的中点
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
// 反转后半部分链表
ListNode prev = null, curr = slow;
while (curr != null) {
ListNode temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
// 比较前半部分和后半部分
ListNode p1 = head, p2 = prev;
while (p2 != null) {
if (p1.val != p2.val) {
return false;
}
p1 = p1.next;
p2 = p2.next;
}
return true;
}
```
时间复杂度:O(n),其中 n 是链表的长度。需要遍历链表两次,时间复杂度是线性的。
空间复杂度:O(1)。只需要常数的额外空间。