3.9 如何判断回文链表

本文对应的力扣题目：

234.回文链表

「回文链表」问题给你输入一个单链表的头结点，请你判断这个链表中的数字是不是回文，函数签名如下：

boolean isPalindrome(ListNode head);

模仿双指针实现回文判断的功能：

// 左侧指针
ListNode left;

boolean isPalindrome(ListNode head) {
    left = head;
    return traverse(head);
}

// 利用递归，倒序遍历单链表
boolean traverse(ListNode right) {
    if (right == null) return true;
    boolean res = traverse(right.next);
    // 后序遍历代码
    res = res && (right.val == left.val);
    left = left.next;
    return res;
}

3.9.2 优化空间复杂度

更好的思路是这样的：

boolean isPalindrome(ListNode head) {
    ListNode slow, fast;
    slow = fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    // slow 指针现在指向链表中点
    if (fast != null)
        slow = slow.next;

    ListNode left = head;
    ListNode right = reverse(slow);

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

其中 reverse 函数就是标准的链表反转算法：

// 反转以 head 为头的链表，返回反转之后的头结点
ListNode reverse(ListNode head) {
    ListNode pre = null, cur = head;
    while (cur != null) {
        ListNode next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}