234. Palindrome Linked List

brute

T: O(n)

S: O(n)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        List<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        int left = 0;
        int right = list.size()-1;
        while (left < right) {
            if (list.get(left) != list.get(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

use slow, fast pointer and reverse linked list

T: O(n)

S: O(1)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 
 while (fast != null && fast.next != null)
 
 use a slow pointer, and a faster pointer
 fast go to the end, 
 1 2 2 1
     s
        f
    
the reverse the slower point part, become this
 1 2
 h
 f  -> fast = head
     1 2 
     s     -> slow
then compare one by one


if is a odd length list (so at last, fast is not null)
1 2 3 2 1
    s
        f    
let s = s.next  => important (because odd length the middle one don't need compare)
1 2 3 2 1
      s
        f 
then reverse slow => 
      1,2 -> 

f = head
1 2
f

only compare 1,2.and 1,2

yes!
if odd numbers, 最中間就不用比了！！！


 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        if (fast != null) {
            slow = slow.next;
        }
        
        ListNode right = reverse(slow);
        ListNode left = head;
        
        while (right != null) {
            if (left.val != right.val) {
                return false;
            }
            left = left.next;
            right = right.next;
        }
        return true;
    }
    
    /*
                 prev  cur  next  
prev    a -> b -> c    null
        a <- b
        
     prev = null cur = head
     
     whi
     
    */
    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
}