思路:通过快慢指针法寻找链表的中点,将后半部分的链表翻转,然后二者相对比
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
if(head == null){
return false;
}
ListNode firstHalfEnd = endOfFirstHalf(head);
ListNode secondHalfStart = reverseLink(firstHalfEnd.next);
ListNode p1 = head;
ListNode p2 = secondHalfStart;
boolean flag = true;
while( p2 != null){
if(p1.val !=p2.val){
flag = false;
break;
}
p1 = p1.next;
p2 = p2.next;
}
firstHalfEnd = reverseLink(secondHalfStart);
return flag;
}
//反转链表
private ListNode reverseLink(ListNode head){
ListNode pre = null;
ListNode cur = head;
while(cur != null){
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
//快慢指针寻找中点
private ListNode endOfFirstHalf(ListNode head){
ListNode slow = head;
ListNode fast = head;
while(fast.next != null && fast.next.next != null){
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}