1ms Java solution with O(1) space and O(n) time


  • 0
    X

    Reverse the first half of the linked list, then start from the middle to both sides, checking whether the elements are the same

    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null)
            return true;
        
        ListNode temp = head;
        int lenth = 0;
        while (temp!=null){
            temp = temp.next;
            lenth++;
        }
        
        ListNode current = head;
        ListNode front = head.next;
        head.next = null;
        int count = 2;
        while (count<=lenth/2){
            ListNode copy = front.next;
            front.next = current;
            current = front;
            front = copy;
            
            count++;
        }
        if (lenth%2 == 1)
            front = front.next;
        
        while (front!=null){
            if (front.val != current.val)
                return false;
            front = front.next;
            current = current.next;
        }
        return true;
    }

Log in to reply
 

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