Accepted Java O(N) solution with O(N) memory


  • 0
    J

    Here is accepted Java solution that uses the simple trick.

    You could check if the list is palidroming by maintaing two pointers one to the beginning and second to the end of the list and iteratively checking if the nodes contain the same value, since the problem requires to process the linked list: finding the kth element from the end of the list each time is not efficient and would end up with O(N ^ 2) solution. We can fix that by doing a copy of the list: a reversed one to be specific.

    Here is the complete solution:

    public class Solution {
        public boolean isPalindrome(ListNode head) {
            if (head == null) {
                return true;
            }
    
            ListNode node = head;
            ListNode reversed = reverse(head);
            while(node != null) {
                if(node.val != reversed.val) {
                    return false;
                }
                reversed = reversed.next;
                node = node.next;
            }
            return true;
        }
        
        private ListNode reverse(ListNode head) {
            ListNode node = head, prev = null;
            while(node != null) {
                ListNode copy = new ListNode(node.val);
                copy.next = prev;
                prev = copy;
                node = node.next;
            }
            return prev;
        }
    }

  • 0
    R

    I am getting TLE error with this method.Can someone please tell me where is the exact problem?

    public boolean isPalindrome(ListNode head) {
                 if(head == null || head.next == null) 
                 return true;
                ListNode node = head;
                ListNode reverseNode = reverse(head);
        
                while (node.next!=null && reverseNode.next!=null){
                    if(node.val!=reverseNode.val){
                        return false;
                    }
                    node = node.next;
                    reverseNode = reverseNode.next;
                }
        
                return true;
        
            }
    
        public ListNode reverse(ListNode head){
            ListNode temp = null;
            ListNode next = null;
            ListNode current = head;
    
            while(current!=null){
                next = current.next;
                current.next = temp;
                temp = head;
                head = next;
            }
    
            return temp;
        }

  • 0
    J

    I don't see why you would have a Time limit exceeded, but I see a potential error here. You can not reverse the original list and than traverse the both ends you need to make a copy this is way I'm calling:

    ListNode copy = new ListNode(node.val);


  • 0
    R

    Yes..thats the catch.Thanks for pointing out.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.