234. Palindrome Linked List

三刷

Version #1 Store the values to a list + two pointers

Time O(N)

Space O(N)

Runtime: 18 ms, faster than 34.96% of Java online submissions for Palindrome Linked List.

Memory Usage: 108.5 MB, less than 16.47% of Java online submissions for Palindrome Linked List.

class Solution {

    public boolean isPalindrome(ListNode head) {

        List<Integer> vals = new ArrayList<>();

        while (head != null) {

            vals.add(head.val);

            head = head.next;

        }

        int left = 0, right = vals.size() - 1;

        while (left < right) {

            if (vals.get(left) != vals.get(right)) {

                return false;

            }

            left++;

            right--;

        }

        return true;

    }

}

Version #2 Reverse the second half

Time O(N)

Space O(1)

Runtime: 4 ms, faster than 97.84% of Java online submissions for Palindrome Linked List.

Memory Usage: 97.8 MB, less than 52.81% of Java online submissions for Palindrome Linked List.

class Solution {

    public boolean isPalindrome(ListNode head) {

        ListNode slow = head, fast = head;

        //           s

        //                    f

        // 1 -> 2 -> 3 -> 4

        while (fast != null && fast.next != null) {

            slow = slow.next;

            fast = fast.next.next;

        }

        // reverse the list between slow and fast

        ListNode prev = null;

        ListNode curr = slow;

        while (curr != null) {

            ListNode next = curr.next;

            curr.next = prev;

            prev = curr;

            curr = next;

        }

        ListNode firstHead = head;

        ListNode secondHead = prev;

        while (secondHead != null) {

            if (firstHead.val != secondHead.val) {

                return false;

            }

            firstHead = firstHead.next;

            secondHead = secondHead.next;

        }

        return true;

    }

}

这个版本slow停在后半段的起点
下面另外写了一个版本是find middle of linked list的通常版本，slow停在的是前半段的终点

版本2 的问题是 slow和prev之间是断开的！这个bug看了好久才发现


One pass同时做三件事
1.找中点
2.判断奇偶
3.Reverse list




Version #1
二刷
完全忘了之前写过这个，自己写了1 pass加reverse
发现判断奇偶只需要看最后fast是不是null
如果fast是null就是偶数
97.71 %
class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode fast = head, slow = head, prev = null, next = null;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            next = slow.next;
            slow.next = prev;
            prev = slow;
            slow = next;
        }
        //    pr s      f
        //<-1<-2 2->1
        //   pr s     f
        // <-1  2 - > 1
        if (fast != null) { // for odd
            slow = slow.next;
        }
        while (slow != null && prev != null) {
            if (slow.val != prev.val) {
                return false;
            }
            slow = slow.next;
            prev = prev.next;
        }
        return true;
    }
}


93.21 %

class Solution {
    public boolean isPalindrome(ListNode head) {
        //<-     s          f
        //  1 -> 2 -> 3 -> null
        //         s             f
        // 1 -> 2 -> 3 -> 4 -> null
        if (head == null) return true;
        ListNode slow = head;
        ListNode fast = head.next;
        boolean isEven = false;
        //  prev  slow next
        //         1 -> 2 -> 3 -> 4 -> 5 -> ...
        // null <- 1 <- 2 <- 3 <- 4  5
        ListNode prev = null;
        ListNode next = null;
        while (fast != null) {
            next = slow.next;
            slow.next = prev;
            prev = slow;
            slow = next;
            fast = fast.next;
            if (fast != null) {
                fast = fast.next;
            } else {
                isEven = true;
            }
        }
        if (isEven) {
            fast = slow;
        } else {
            fast = slow.next;
        }
        slow = prev;
        while (fast != null) {
            if (slow.val != fast.val) return false;
            slow = slow.next;
            fast = fast.next;
        }
        return true;
     
    }
}

Version #2
 93.21 %
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null) return true;
        //    s     f
        // 1->2->3->4->null
        //    s      f
        // 1->2->3->null
     
        ListNode slow = head;
        ListNode fast = head.next;
        ListNode prev = null;
        ListNode next = slow.next;
        // prev slow next
        // null  1 -> 2  -> 3 -> 4 -> null
        while (fast != null && fast.next != null) {
            next = slow.next;
            slow.next = prev;
            prev = slow;
            slow = next;
            fast = fast.next.next;
        }
        if (fast == null) {
            fast = slow.next;
            slow = prev;
        } else {
            fast = slow.next;
            slow.next = prev;
        }
     
     
        while (fast != null) {
            //System.out.println(slow.val + " " + fast.val);
            if (slow.val != fast.val) return false;
            slow = slow.next;
            fast = fast.next;
        }
        return true;
     
    }
}