请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶:
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?
class Solution {
//反转链表
public ListNode reverseList(ListNode head){
ListNode curr = head, pre = null;
while(curr != null){
ListNode temp = curr.next;
curr.next = pre;
pre = curr;
curr = temp;
}
return pre;
}
public boolean isPalindrome(ListNode head) {
if(head == null){
return false;
}
//找到中间节点,1,3,4,5,4,3,1
//遍历完后,curr指向节点5
ListNode curr = head, temp = head;
while(temp != null && temp.next != null){
curr = curr.next;
temp = temp.next.next;
}
//将curr指向的后半段链表反转,反转后的链表为1,3,4,1,3,4,5
temp = reverseList(curr);
while(temp != null){
//从头开始与head链表比较
if(head.val != temp.val){
return false;
}
head = head.next;
temp = temp.next;
}
return true;
}
}