题解 1 的解法使用了辅助空间，在可以改变原来的链表的基础上，可使用原地翻转，思路为翻转前半部分，然后迭代比较。具体可分为以下四个步骤。

1. 找中点。
2. 翻转链表的后半部分。
3. 逐个比较前后部分节点值。
4. 翻转后半部分链表，链表复原。

Java

/**
 * Definition for singly-linked list.
 */
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Solution {
    public static boolean isPalindrome(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        // push node before mid
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // skip mid node for odd number
        if (fast != null) {
            slow = slow.next;
        }

        ListNode rightHead = reverse(slow);
        ListNode rCurr = rightHead;
        ListNode lCurr = head;
        while (rCurr != null) {
            if (rCurr.val != lCurr.val) {
                return false;
            }
            lCurr = lCurr.next;
            rCurr = rCurr.next;
        }
        // recover list
        rightHead = reverse(rightHead);

        return true;
    }

    public static ListNode reverse (ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode temp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = temp;
        }

        return prev;
    }

    public static void main (String[] args) {
        int len = 9;
        ListNode head = new ListNode(0);
        ListNode node = head;
        for (int i = 1; i < 9; i++) {
            int temp = (i >= len / 2) ? (len - i - 1) : i;
            node.next = new ListNode(temp);
            node = node.next;
        }

        System.out.println(isPalindrome(head));
    }
}

C++

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (!head || !head->next) return true;  

        // find middle
        ListNode* slow = head, *fast = head;
        while (fast && fast->next) {               
            slow = slow->next;
            fast = fast->next->next;
        }

        // skip mid node if the number of ListNode is odd
        if (fast) slow = slow->next;    

        // reverse right part of List
        ListNode* rHead = reverse(slow);  
        ListNode* lCurr = head, *rCurr = rHead;
        while (rCurr) {
            if (rCurr->val != lCurr->val) {
                reverse(rHead);
                return false;
            }
            lCurr = lCurr->next;
            rCurr = rCurr->next;
        }
        // recover right part of List
        reverse(rHead);            

        return true;
    }

    ListNode* reverse(ListNode* head) {
        ListNode* prev = NULL;
        while (head) {                           
            ListNode* after = head->next;   
            head->next = prev;
            prev = head;
            head = after;
        }
        return prev;
    }
}

源码分析

连续翻转两次右半部分链表即可复原原链表，将一些功能模块如翻转等尽量模块化。

复杂度分析

遍历链表若干次，时间复杂度近似为 O(n), 使用了几个临时遍历，空间复杂度为 O(1).

题解3 - 递归（LTE）

递归需要两个重要条件，递归步的建立和递归终止条件。对于回文比较，理所当然应该递归比较第 i 个节点和第 n-i 个节点，那么问题来了，如何构建这个递归步？大致可以猜想出来递归的传入参数应该包含两个节点，用以指代第 i 个节点和第 n-i 个节点。返回参数应该包含布尔值(用以提前返回不是回文的情况)和左半部分节点的下一个节点(用以和右半部分的节点进行比较)。由于需要返回两个值，在 Java 中需要使用自定义类进行封装，C/C++ 中则可以使用指针改变在递归调用后进行比较时节点的值。

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

class Result {
    ListNode lNode;
    boolean isP;
    Result(ListNode node, boolean isP) {
        this.lNode = node;
        this.isP = isP;
    }
}

public class Solution {
    /**
     * @param head a ListNode
     * @return a boolean
     */
    public boolean isPalindrome(ListNode head) {
        Result result = new Result(head, true);
        helper(head, result);

        return result.isP;
    }

    private void helper(ListNode right, Result result) {
        if (right != null) {
            helper(right.next, result);
            boolean equal = (result.lNode.val == right.val);
            result.isP = equal && result.isP;
            result.lNode = result.lNode.next;
        }
    }
}

源码分析