Pretty silly but straight forward solution using stack in Java


  • 0
    F

    So the idea is to push half of the list value into a stack.
    And then peek to see if the next element have the same value.
    When the stack is empty, it means that the linked list is palindrome

    public boolean isPalindrome(ListNode head) {
        if(head==null||head.next==null) return true;
        
        int count = 1;
        ListNode dummy = head;
        ListNode comp = head;
        while(dummy.next!=null){
            count++;
            dummy=dummy.next;
        }
        
        Stack<Integer> temp = new Stack<Integer>();
        
        //if the count is even, we push half of the list into the stack for comparing
        if(count%2==0){
            int n=count/2;
            while(n!=0){
                temp.push(comp.val);
                n--;
                comp=comp.next;
            }
            //if the number on the top of the stack equals to the next number, then pop it and move on
            while(comp.val==temp.peek()){
                temp.pop();
                if(comp.next!=null){
                    comp=comp.next;
                } else break;
            }
            return temp.empty();
        }
        
        //if the count is odd, we push count/2-1 of the list into the stack for comparing
        else {
            int n=count/2;
            while(n!=0){
                temp.push(comp.val);
                n--;
                comp=comp.next;
            }
            //this is for skipping the node in the middle
            comp=comp.next;
            while(comp.val==temp.peek()){
                temp.pop();
                if(comp.next!=null){
                    comp=comp.next;
                } else break;
            }
            return temp.empty();
        }
    }

  • 0
    V

    1 optimization would be to create the stack ALONG with keeping the value in count variable itself and after that we could do len=len/2 ... and then check only first half of linked list with the first half of stack .


Log in to reply
 

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