234. 回文链表 234. Palindrome Linked List

[Shellbye]

题目描述

请判断一个链表是否为回文链表。
示例 1:

输入: 1->2
输出: false

示例 2:

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

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

空间复杂度 O(n) 的解法

这个题目本身并算不上难题， O(n) 的时间复杂度也是没得跑，关键就是空间复杂度了，那么先上一个需要 O(n) 空间复杂度的解法：

    public boolean isPalindrome(ListNode head) {
        ListNode slow = head;
        List<ListNode> list = new ArrayList<>();
        while (slow.next != null) {
            list.add(slow);
            slow = slow.next;
        }
        Collections.reverse(list);
        ListNode l = head;
        for (ListNode n : list) {
            if (n.val != l.val) {
                return false;
            }
            l = l.next;
        }
        return true;
    }

这基本是入门程序员都可以写出来的，所以这个题目加了一个“进阶”，只使用常数空间。

快慢指针

链表相关的题目都经常用到的一快一慢双指针，通过这个双指针，我们可以定位到链表的中间位置。但是因为双指针的起点的不同，以及链表长度的奇偶不同，会有一些细节上的差异。比如如下情况，其中 N 表示一个节点，fn 表示快指针 fast 第 n 步的位置，sn同理

f0--------f1--------f2
N -> N -> N -> N -> N -> null
s0--s1---s2

链表长度为奇数的情况下，快指针指向最后一个元素，慢指针指向中间元素；

f0--------f1--------f2---------f3
N -> N -> N -> N -> N -> N -> null
s0--s1---s2---s3

链表长度为偶数的情况下，快指针指向 null，慢指针指向第 n/2 + 1 个元素；

空间复杂度 O(1) 的解法

很多算法都有“拿时间换空间”或者“拿空间换时间”的说法，在这个题里，空间减少的同时，因为相关操作的减少，所以时间上反而也减少了。
首先是通过快慢指针定位中间位置，然后比较前半段和后半段了，因为回文的特殊性，我们需要反转某半段链表，才能方便的进行比较。代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        // 参数校验
        if (head == null || head.next == null) {
            return true;
        }

        // 寻找中间位
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        ListNode p2;
        // 确定后半段的起点
        if (fast == null) {
            // 链表长度为偶数，slow 指向后半段的开始
            p2 = slow;
        } else {
            // 链表长度为奇数，slow 指向中间值
            p2 = slow.next;
        }

        // 反转前半段
        ListNode pre = null;
        ListNode cur = head;
        while (cur != slow) {
            // 保存当前节点的下一个
            ListNode next = cur.next;
            // 下一个改为指向前一个
            cur.next = pre;
            //
            pre = cur;
            // 处理下一个
            cur = next;
        }


        // 比较
        while (pre != null) {
            if (pre.val != p2.val) {
                return false;
            }
            pre = pre.next;
            p2 = p2.next;
        }

        return true;
    }
}