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?

解题方法

way1:

1. 透過fast/slow 找到中點
2. 從中間開始判斷奇偶數決定往旁邊比對 （左邊需要reverse）

way2: （Recommand）

1. 透過fast/slow 找到中點
2. 從尾端開始往中間比對 （右邊需要reverse ）

但因此不用判斷奇偶個數，因為比對到tail == null 就會結束

 public boolean isPalindrome(ListNode head){
        if(head == null || head.next == null){  return true;}

        ListNode mid = findMiddle(head);
        ListNode tail = reverse(mid.next);
        while( head != null && tail != null && head.val == tail.val){
            head = head.next;
            tail = tail.next;
        }
        return tail == null;
    }

    private ListNode findMiddle(ListNode head){
        ListNode slow = head;
        ListNode fast = head.next;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    private ListNode reverse(ListNode head){
        ListNode pre = null;
        while(head != null){
            ListNode temp = head.next;
            head.next = pre;
            pre = head;
            head = temp;
        }
        return pre;
    }