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?
Could you do it in O(n) time and O(1) space?
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
ListNode p1 = head;
ListNode p2 = head;
while (p2.next != null && p2.next.next != null) {
p1 = p1.next;
p2 = p2.next.next;
}
ListNode head2 = p1.next;
p1.next = null;
// reverse head2;
ListNode pre = null;
ListNode p = head2;
while (p != null) {
ListNode nextP = p.next;
p.next = pre;
pre = p;
p = nextP;
}
ListNode newHead2 = pre;
p1 = head;
p2 = newHead2;
while (p1 != null && p2 != null) {
if (p1.val != p2.val) {
return false;
}
p1 = p1.next;
p2 = p2.next;
}
return true;
}
}
没有评论:
发表评论