LeetCode题解-链表标签：回文链表

题目：请判断一个单向链表是否为回文链表。

Leetcode在线OJ系统：传送门

示例1：

graph LR
A[1]-->B[2]

输出：false

示例2:

graph LR
A[1]-->B[2]
B[2]-->C[2]
C[2]-->D[1]

输出：true

思路：

首先需要知道什么是“回文”：回文指的是无论正向还是反向读，得到的结果一致。由于单向链表的特点，如果我们直接读原链表，则只能正向读取，无法进行判断。所以我们需要进行一定的转化。

转换方式一：将整个单向链表映射到一个数组中，然后使用两个指针分别从数组两端开始遍历，当遇到数值不相等的节点时，可断定为非回文链表，如果遍历到两个节点相遇时都未发现数值不相等的节点，则为回文链表。

单链表节点类定义可查看文章：数据结构之链表-基础知识

Java语言实现如下：

public static boolean isPalindrome(SinglyLinkedListNode head) {
    List<SinglyLinkedListNode> list = new ArrayList<>();
    while (head != null) {
        list.add(head);
        head = head.next;
    }
    for (int i = 0,size = list.size();i < size / 2;i++) {
        if (!list.get(i).val.equals(list.get(size - i - 1).val)) {
            return false;
        }
    }
    return true;
}

这种方式的空间复杂度为O(n)，时间复杂度为O(n + n/2) = O(n)。

转换方式二：不使用额外空间，我们在原链表上做文章，如果一个单向链表为回文链表，我们可以先将前半段链表进行反转，然后再使用两个指针p1和p2，p1从头部开始，p2从中间开始，遍历链表，当遇到数值不相等的节点，可断定为非回文链表；如果p2遍历到尾部都还未遇到数值不相等的节点，则为回文链表。

如何将前半段链表进行反转？可利用一快一慢两个指针先找到中间节点，然后将从头节点开始到中间节点的这一部分进行反转。

Java语言实现如下：

public static boolean isPalindromeUseReverse(SinglyLinkedListNode head) {
    if (head == null || head.next == null) {
        return true;
    }
    // 快慢指针
    SinglyLinkedListNode fast = head;
    SinglyLinkedListNode slow = head;
    // 快指针走到末尾时，慢指针指向中间节点
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    // 反转从头节点到中间节点之间的部分
    SinglyLinkedListNode p1 = head;
    SinglyLinkedListNode p2 = slow;
    SinglyLinkedListNode pre = slow;
    SinglyLinkedListNode next;
    while (p1 != p2) {
        next = p1.next;
        p1.next = pre;
        pre = p1;
        p1 = next;
    }
    // 如果原链接节点个数为奇数，则中间节点p2（slow）需要右移一位才能进行回文比较
    // 例如：1->2->3->2->1；反转前半部分后为：2->1->3->2->1
    // p2指向中间节点3，需要右移一位指向2，才能进行回文比较
    if (fast != null) p2 = p2.next;
    // 此时pre指向新链表的头节点
    while (p2 != null) {
        if (!pre.val.equals(p2.val) {
            return false;
        }
        pre = pre.next;
        p2 = p2.next;
    }
    return true;
}

此方式的时间复杂度为：O(n + n/2 + n/2) = O(n)，空间复杂度为O(1)。

缺点是改变了原链表的结构，但可在判断出是否为回文链表后再次反转前半部分节点，从而恢复原链表的结构。

方式二的优化版本：使用快慢指针寻找中间节点的过程中慢指针已经遍历了前半部分链表，可就在这一次的遍历中进行反转。

优化后的代码实现如下：

public static boolean isPalindromeUseReverseOptimization(SinglyLinkedListNode head) {
    if (head == null || head.next == null) {
        return true;
    }
    SinglyLinkedListNode fast = head;
    SinglyLinkedListNode slow = head;
    SinglyLinkedListNode pre = null;
    SinglyLinkedListNode next;
    // 慢指针移动的同时进行反转
    while (fast != null & fast.next != null) {
        fast = fast.next.next;
        next = slow.next;
        slow.next = pre;
        pre = slow;
        slow = next;
    }
    if (fast != null) slow = slow.next;
    while (slow != null) {
        if (!pre.val.equals(slow.val)) return false;
        pre = pre.next;
        slow = slow.next;
    }
    return true;
}