面试题 02.06. 回文链表

面试题 02.06. 回文链表

难度简单78

编写一个函数，检查输入的链表是否是回文的。

示例 1：
输入： 1->2
输出： false

示例 2：
输入： 1->2->2->1
输出： true

进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题

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

        ListNode mid = middleNode(head);
        ListNode rHead = reverse(mid.next);
        ListNode lHead = head;

        while(rHead!=null){
            if(lHead.val != rHead.val) return false;
            rHead = rHead.next;
            lHead = lHead.next;
        }
        return true;
    }

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

    }
    public ListNode reverse(ListNode head){

            ListNode newHead = null;
            while(head !=null){
                ListNode tmp = head.next;
                head.next = newHead;
                newHead=head;
                head=tmp;
            }
            return newHead;
    }
}