Given a singly linked list, determine if it is a palindrome.
Example 1:
Input: 1->2 Output: false
Example 2:
Input: 1->2->2->1 Output: true
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?
Java Solution :
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
if(head == null || head.next == null)
return true;
ListNode prev = new ListNode(head.val);
ListNode dummy = head;
while(dummy.next != null){
ListNode temp = new ListNode(dummy.next.val);
temp.next = prev;
prev = temp;
dummy = dummy.next;
}
ListNode last = prev;
ListNode first = head;
while(first!=null && last!=null){
if(first.val == last.val){
first = first.next;
last = last.next;
}else{
return false;
}
}
return true;
}
}
No comments:
Post a Comment