LeetCode.234.Palindrome Linked List 判断是否回文单链表

题目描述

234 Palindrome Linked List
https://leetcode-cn.com/problems/palindrome-linked-list/

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

Example 1:

Input: 1->2
Output: false

Example 2:

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

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

---

解题过程

判断是否回文单链表

递归反向遍历

判断是否回文就需要正向遍历和反向遍历后比较，由于题目不让用额外空间，所以无法把链表反转后存储到一个新链表中。
由于 递归遍历可以实现从后往前的倒序访问，就想到递归反向遍历的同时，维护一个全局正向遍历的指针，每次递归访问结点时和正向指针比较。
注意，虽然递归写法中只维护了一个正向遍历指针，但空间复杂度并不是 O(1)，因为递归要用到一个大小为n的栈，所以空间复杂度还是 O(n)，并不是最优解。
虽然递归方法不是最优解，但思想很值得学习，是一个技巧性很强的解法。
时间复杂度 O(n)，空间复杂度 O(n)

private static class SolutionV2020 {
    // 全局正向遍历指针
    private ListNode cur;
    public boolean isPalindrome(ListNode head) {
        if (null == head || null == head.next) {
            return true;
        }
        cur = head;
        return isPalindromeRecursive(head);
    }

    // 递归倒序遍历head，同时和全局正向遍历指针cur比较，返回是否相等
    private boolean isPalindromeRecursive(ListNode head) {
        if (null == head) {
           return true;
        }
        boolean isPalindrome = isPalindromeRecursive(head.next) && (head.val == cur.val);
        cur = cur.next;
        return isPalindrome;
    }
}

双指针找中点反转后半段

我的第一个思路就是用 2倍速双指针，fast一次走2步，slow一次1步，找到链表中间点，然后反转链表后半段，再比较从头开始遍历和从中间点开始遍历的结果，但写起来感觉挺麻烦的，而且有些边界要处理。
没想到看题解后发现这个才是最优解。
时间复杂度 O(n)，空间复杂度 O(1)

---

GitHub代码

algorithms/leetcode/leetcode/_234_PalindromeLinkedList.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_234_PalindromeLinkedList.java

---