Java solution, O(n) time and O(1) space, using reverse function, maintain the source linkedlist not changed, beautiful code


  • 0
    public ListNode reverse(ListNode head) {
        if (head == null) return head;
        ListNode cur = head.next;
        head.next = null;
        while (cur != null) {
        	ListNode tmp = head;
        	head = cur;
        	cur = cur.next;
        	head.next = tmp;
        }
        return head;
    }
    
    /* change list from 1->2->3->2->1 to 1->2->3<-2<-1 */
    public boolean isPalindrome2(ListNode head) {
        if (head == null || head.next == null) return true;
        ListNode tail, pl = head, pr = head;
        while (pr.next != null && pr.next.next != null) {
        	pl = pl.next;
        	pr = pr.next.next;
        }
        pr = tail = reverse(pl.next);
        pl = head;
        while (pr != null && pl.val == pr.val) {
            pl = pl.next;
            pr = pr.next;
        }
        reverse(tail);
        return (pr == null);
    }

Log in to reply
 

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