234. Palindrome Linked List

234. Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Follow up: Could you do it in O(n) time and O(1) space?

My Solutions:

方法1: 把数字复制到一个arraylist里，然后用两个指针在arraylist里确定是否是palindrome

Time: O(n); Space: O(n)

方法2:分三步：

• 找到后半部分 (findMiddle)

• 反转后半部分 (reverse)

• 比较前后部分是否相同 （因为mid导致后半可能比前半少1，最后判断 p2 == null）

public class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null) return true;
        
        ListNode middle = findMiddle(head);
        // 因为这里是从middle.next反转，后半会比前半少1
        // ex1. 1st half is [1,2,3], 2nd half is [4,5]
        // ex2. 1st half is [1,2,3], 2nd half is [4,5,6] 
        middle.next = reverse(middle.next);
        
        ListNode p1 = head, p2 = middle.next;
        while (p1 != null && p2 != null && p1.val == p2.val) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p2 == null;
    }
    
    // 这里返回的slow是靠左边的
    // ex1. [1,2,3,4,5] -> slow is at 3
    // ex2. [1,2,3,4,5,6] -> slow is at 3
    private ListNode findMiddle(ListNode head) {
        if (head == null) return null;
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    
    private ListNode reverse(ListNode head) {
        ListNode prev = null; 
        while (head != null) {
            ListNode temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        }
        return prev;
    }
}