回文链表

一遍过我还是很开心的

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

Example 1:

Input: 1->2
Output: false

Example 2:

Input: 1->2->2->1
Output: true

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

注意空节点和单节点返回的是true

Mine

class Solution {
    public boolean isPalindrome(ListNode head) {
        int length = 0;
        int i = 0;
        ListNode count = head;
        ListNode count2 = head;
        while (count != null) {
            count = count.next;
            length++;
        }
        if (length <= 1) {
            return true;
        }

        while (i <= length / 2) {
            count = head;
            int n = 0;

            while (n < length - i - 1) {
                count = count.next;
                n++;
            }

            if (count2.val != count.val) {
                return false;
            }
            count2 = count2.next;
            i++;
        }

        return true;
    }
}

就是最简单的比对法，慢得不得了，但是这次我写完没测试就提交了，结果居然通过了！

Standard Answer

这里个个都是人才啊！

class Solution {
    public boolean isPalindrome(ListNode head) {
         //1.判断是否是一个节点
        if (head == null || head.next == null)  return true;
        //2判断是否是2个节点
        if (head.next.next == null) return head.val == head.next.val;
        //如果都不是
        //1.设定一个slow指针指向当前回文遍历的字符，设定一个fast指针，遍历到slow对应回文的后面的节点的前一个节点，也就是fast.next.val==slow.val
        ListNode slow = head, fast = head.next;
        //2.这样不断循环推进slow，然后把fast设置为slow.next开始遍历，循环后退，每次匹配成功，然后就把fast后面的断开，并把slow推进
        //如果匹配不成功，则继续推进fast到fast.next==null位置说明没有位置匹配了
        while (fast.next != null) {
            if (slow.val == fast.next.val) {
                //如果匹配成功
                if (fast.next.next != null) {
                    //如果不是和最后一个位置的字符匹配，说明回文中间掺杂其他字符，不连续
                    return false;
                } else {
                    fast.next = null;
                    slow = slow.next;
                    fast = slow.next;
                }
                //判断是否循环结束,这里区分奇和偶，如果是奇数个回文
                if (fast == null || (fast.next == null && slow.val == fast.val)) {
                    return true;
                }
            } else {
                fast = fast.next;
            }
        }
        return false;
    }
}

Answer 2

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null){
            return true;
        }
        // 得到中点/中点前的节点
        ListNode endOfFirstHalf = endOfFirstHalf(head);
        // 翻转后半部分
        ListNode beginOfSecondHalf = reverseNode(endOfFirstHalf.next);

        // 开始比较
        boolean isPalindrome = true;
        ListNode p1 = head;
        ListNode p2 = beginOfSecondHalf;
        while(isPalindrome && p2 != null){
            if(p1.val != p2.val) isPalindrome = false;
            p1 = p1.next;
            p2 = p2.next;
        }
        // endOfFirstHalf.next = reverseNode(beginOfSecondHalf);

        return isPalindrome;
        


    }

    private ListNode reverseNode(ListNode head){
        ListNode prev = null;
        ListNode current = head;
        while(current != null){
            // 临时存储下个节点
            ListNode tempNextNode = current.next;
            // 当前节点next指针指向前节点
            current.next = prev;
            // prev,current指针后移
            prev = current;
            current = tempNextNode;
        }
        return prev;
    }

    private ListNode endOfFirstHalf(ListNode head){
        ListNode slow = head;
        ListNode fast = head;

        // 慢指针每次走一步，快指针每次走两步
        // 若节点为基数，则中点为前半部分
        while(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }
}