class Solution {
public boolean isPalindrome(ListNode head) {
ListNode dummyHead = new ListNode(0, head);
ListNode slow = dummyHead;
ListNode fast = dummyHead;
/**
* 快慢指针找到中间节点
* 因为要反转右区间,如果长度为奇数时,中间节点得分在左区间,这样才能找到右区间的头节点
* 偶数时就是左区间的最后一个元素
*/
while (fast != null && fast.next != null){
fast = fast.next;
slow = slow.next;
if (fast != null && fast.next != null){
fast = fast.next;
}
}
/**
* 让左区间的最后一个元素slow指向null
* 然后反转右区间
*/
ListNode next = slow.next;
slow.next = null;
ListNode rigthHead = reverse(next);
/**
* 依次比较两个区间的节点大小
*/
while (head != null && rigthHead != null){
if (head.val != rigthHead.val){
return false;
}
head = head.next;
rigthHead = rigthHead.next;
}
return true;
}
public ListNode reverse(ListNode head){
ListNode prev = null;
ListNode cur = head;
while (cur != null){
ListNode temp = cur.next;
cur.next = prev;
prev = cur;
cur = temp;
}
return prev;
}
}
/**
* 时间复杂度 O(n)
* 空间复杂度 O(1)
*/
https://leetcode-cn.com/problems/palindrome-linked-list/