My AC java solution with time O(n) and space O(1), and 1 iteration


  • 0
    C
    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }
        ListNode left = null;
        ListNode right = null;
        ListNode slow = head;
        ListNode fast = head;
        ListNode tmp;
        while (fast != null && slow != null) {
            tmp = slow;
            if (fast.next != null && fast.next.next != null) {
                slow = slow.next;
                fast = fast.next.next;
                tmp.next = left;
                left = tmp;
            } else if (fast.next == null) {
                right = slow.next;
                fast = null;
            } else if (fast.next.next == null) {
                right = slow.next;
                tmp.next = left;
                left = tmp;
                fast = null;
            }
        }
        while (left != null && right != null) {
            if (left.val != right.val) {
                return false;
            }
            left = left.next;
            right = right.next;
        }
        return true;
    }

Log in to reply
 

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