题目

给你一个单链表的头节点 head ，请你判断该链表是否为

回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true

示例 2：

输入：head = [1,2]
输出：false

提示：

• 链表中节点数目在范围[1, 105] 内
• 0 <= Node.val <= 9

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

解法

解法一 将后半部分链表反转

1. 遍历一次得到长度
2. 将后半部分反转
3. 从头尾开始双指针对向遍历，如果有不一致的就false

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        // 1. 遍历一次得到长度
        int length = 0;
        ListNode temp_head = head;
        while (temp_head != null) {
            length++;
            temp_head = temp_head.next;
        }
        if (length == 1) return true;
        // 2. 将后半反转
        int middle = (length - 1) / 2;
        // 实际上不需要区分奇数长度和偶数长度
        // 2.1 找到后半的起始点作为反转的cur
        ListNode cur = head, pre = null;
        for (int i = 0; i < middle + 1; i++) {
            cur = cur.next;
        }
        // 2.2 反转链表
        while (cur.next != null) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        cur.next = pre;

        // 3. 从两边遍历看是否一致
        while (cur != null && head != null) {
            if (cur.val != head.val) return false;
            cur = cur.next;
            head = head.next;
        }
        return true;

    }
}

时间复杂度为O(N)，因为是原地操作，空间复杂度为O(1)

优化 – 快慢指针 优化掉 找长度

慢指针走一步，快指针走两步，快指针走到头的时候，慢指针刚好走到中间，省去得到长度的那个遍历，直接找到后半链表的起始点。

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head.next == null) return true;
        // 1. 快慢指针
        int length = 0;
        ListNode slow = head, fast = head.next;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        if (fast.next != null) {
            fast = fast.next;
        }
        slow = slow.next;
        // 到这里，slow指向后半开头，fast指向末尾
        // 2. 将后半反转
        ListNode cur = slow, pre = null;
        // 2.2 反转链表
        while (cur.next != null) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        cur.next = pre;

        // 3. 从两边遍历看是否一致
        while (cur != null && head != null) {
            if (cur.val != head.val) return false;
            cur = cur.next;
            head = head.next;
        }
        return true;
    }
}