反转链表 + 双指针
思路:先算出链表总共多长,然后反转一半,然后再双指针比较即可,注意下引用的细节即可
劣质代码
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode l = new ListNode();
ListNode r = new ListNode();
int n = 0;
l = head;
while(l != null) {
n ++;
l = l.next;
}
l = new ListNode();
l.next = head;
int k = n / 2;
while(k -- > 0) l = l.next;
if(n % 2 == 1) l = l.next;
l = l.next;
while(l != null) {
ListNode temp = l.next;
l.next = r.next;
r.next = l;
l = temp;
}
while(r.next != null) {
if(r.next.val != head.val) return false;
r = r.next;
head = head.next;
}
return true;
}
}
思路优化: 通过快慢指针定位中点,一个指针一次都一步,一个指针一次都两步,那么快指针走到链表尾时,慢指针刚好到达中点,这样时间复杂度少了$O(n / 2)$
优质代码
public class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
// 1. Find the middle of the list
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 2. Reverse the second half
ListNode prev = null, curr = slow;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
// 3. Compare the two halves
while (prev != null) {
if (head.val != prev.val) return false;
head = head.next;
prev = prev.next;
}
return true;
}
}