Java实现给你一个单链表的头节点 head = [1,2,2,1] ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。完整代码
时间: 2024-09-20 07:05:42 浏览: 44
在Java中,判断一个单链表是否为回文链表可以通过双指针技巧来实现,即一个指针从头开始向前移动,另一个指针从尾部开始向后移动,同时比较两个指针指向的节点值。如果链表长度为奇数,中间节点不需要比较,因为只有一个;如果链表长度为偶数,则需要比较中间两个节点。以下是具体的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;
ListNode fast = head.next;
// 找到链表的中间节点(或中间两个节点)
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 双指针法比较
ListNode start = slow;
while (start != null) {
if (start.val != fast.val) {
// 如果找到不相等的节点,不是回文
return false;
}
start = start.next;
fast = fast.next;
}
// 链表是回文
return true;
}
```
阅读全文