题目234. Palindrome Linked List
Given a singly linked list, determine if it is a palindrome.
Follow up:
Could you do it in O(n) time and O(1) space?
思路:使用快慢指针,找到链表的中点,然后将后半部逆转.
最后前后两部分的元素逐个进行对不
public class Solution {
public boolean isPalindrome(ListNode head) {
//快慢指针, lower到中点, 然后后半部分逆转. 然后分别比较这两部分的值即可
if(head == null || head.next == null){
return true;
}
if(head.next.next == null){
return head.val == head.next.val;
}
ListNode lowerNode = head;
ListNode fastNode = head;
while(fastNode.next != null && fastNode.next.next != null){
lowerNode = lowerNode.next;
fastNode = fastNode.next.next;
}
ListNode secondNode = lowerNode.next;
lowerNode.next = null;
ListNode secondHead = new ListNode(1);
ListNode tempNode = null;
while(secondNode != null){
tempNode = secondNode.next;
secondNode.next = secondHead.next;
secondHead.next = secondNode;
secondNode = tempNode;
}
secondNode = secondHead.next;
ListNode firstNode = head;
while(secondNode != null){
if(secondNode.val != firstNode.val){
return false;
}
firstNode = firstNode.next;
secondNode = secondNode.next;
}
return true;
}
}