Reverse then compare and restore -- Java version


  • 0
    Y
    public static boolean isPalindrome(ListNode head) {
    	if (head == null) return true;
    	boolean isP = true;
        ListNode fast = head;
        ListNode pre = head;
        ListNode cur = head;
        ListNode nex = head.next;
    
        // reverse first half
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
    
            pre = cur;
            cur = nex;
            nex = nex.next;
            cur.next = pre;
        }
    
        ListNode cur2 = nex;
        nex = pre;
        pre = cur2;
        // if odd number of nodes, need to move left one 
        if (fast.next == null) {
        	cur.next = pre;
        	pre = cur;
        	cur = nex;
        	nex = nex.next;
        }
    
        // compare and restore
        while (cur2 != null) {
        	isP = isP && cur2.val == cur.val;
    
        	cur2 = cur2.next;
    
        	cur.next = pre;
        	pre = cur;
        	cur = nex;
        	nex = nex.next;
        }
    
        return isP;
    }

Log in to reply
 

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