题目

请判断一个链表是否为回文链表。

示例 1:

1 2	输入: 1->2 输出: false

示例 2:

1 2	输入: 1->2->2->1 输出: true

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

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

Example 1:

1 2	Input: 1->2 Output: false

Example 2:

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

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

解题方法

反转链表

新建一个原来链表的反转链表，然后将两个链表节点逐一比较，O(n)时间复杂度，O(n)空间复杂度，可以不破坏原链表。这段代码跑了2ms，超过了78.51%的Java提交。

class Solution {
    // Method 1 2ms 78.51%
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        ListNode headBackup = head;
        ListNode tail = null;
        ListNode tmp = tail;
        while (head != null) {
            tail = new ListNode(head.val);
            tail.next = tmp;
            tmp = tail;
            head = head.next;
        }
        while (headBackup != null) {
            if (headBackup.val != tail.val) {
                return false;
            }
            headBackup = headBackup.next;
            tail = tail.next;
        }
        return true;
    }
}

反转一半

先扫描一次链表得到链表长度，然后翻转链表前半部分，然后前后两部分进行比较，需要注意的是，长度为奇数时，中间节点可以跳过。时间复杂度O(n)，空间复杂度O(1)，但是会破坏原链表。这段代码跑了1ms，超过了98.12%的Java提交。

class Solution {
    // Method 2 1ms 98.12%
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
	      
      	// length of the linked list
        int count = 1;
        ListNode counter = head;
        while (counter.next != null) {
            count++;
            counter = counter.next;
        }
        int n = count / 2;

      	// reverse the left half of the linked list
        ListNode tail = head.next;
        head.next = null;
        for (int i = 1; i < n; i++) {
            ListNode tmp = tail.next;
            tail.next = head;
            head = tail;
            tail = tmp;
        }

      	// skip the middle node when count is odd
        if (count % 2 == 1) {	
            tail = tail.next;
        }

        while (tail != null) {
            if (head.val != tail.val) {
                return false;
            }
            tail = tail.next;
            head = head.next;
        }

        return true;
    }
}