JAVA O(N) & O(1)


  • 0
    S
    public class Solution {
        public boolean isPalindrome(ListNode head) {
            if (head == null) return true;
            int length = 1;
            ListNode end = head;
            while (end.next != null) {
                end = end.next;
                length++;
            }
            int half = length/2;
            
            ListNode pre = null;
            ListNode cur = head;
            ListNode next = head.next;
            
            for(int i=1; i<=half; i++) {
                cur.next = pre;
                pre = cur;
                cur = next;
                next = cur.next;
            }
            if (length % 2 == 1) cur = next;
            
            for(int i=1; i<=half; i++) {
                if (pre.val != cur.val) return false;
                pre = pre.next;
                cur = cur.next;
            }
            return true;
        }
    }

Log in to reply
 

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