对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900。
//测试样例:
//1->2->2->1
//返回:true
public boolean chkPalindrome() {
// write code here
ListNode fast = this.head;
ListNode slow = this.head;
if (this.head == null){
return false;
}
if (this.head.next == null){
//只有头节点自己,必然是回文
return true;
}
//找到中间
while (fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
//反转后半段
ListNode cur =slow.next;
while (cur != null){
ListNode curNext = cur.next;
cur.next = slow;
slow = cur;
cur = curNext.next;
}
//此时slow是最后一个了
while (slow != this.head){
if (this.head.val != slow.val){
return false;
}
if (this.head.next == slow){
return true;
}
slow = slow.next;
this.head = this.head.next;
}
return true;
}