Palindrome Linked List - LeetCode

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?
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

Featured Post

H1B Visa Stamping at US Consulate

  H1B Visa Stamping at US Consulate If you are outside of the US, you need to apply for US Visa at a US Consulate or a US Embassy and get H1...