Java O(n) time complexity, O(1) space


  • 0
    Z
    public boolean isPalindrome(ListNode head) {
            if (head == null || head.next == null) {
                return true;
            }
            // in place
            // step 1: find the middle point
            ListNode mid = findMid(head);
            // step 2: reverse the right part
            ListNode newHead = reverse(mid.next);
            // step 3: compare left part and right part, right part length <= left part
            while (newHead != null) {
                if (head.val != newHead.val) {
                    return false;
                }
                head = head.next;
                newHead = newHead.next;
            }
            return true;
        }
        
        private ListNode findMid(ListNode head) {
            ListNode slow = head;
            ListNode fast = head;
            while (fast.next != null && fast.next.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            return slow;
        }
        
        private ListNode reverse(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            ListNode pre = null;
            ListNode cur = head;
            while (cur != null) {
                ListNode next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            return pre;
        }
    

Log in to reply
 

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