数据结构与算法 ---- 判断链表是否为回文结构的三种高效解法

简单回顾一下链表的结构~

一、链表的节点结构

1.单链表的节点结构

Class Node<V>{
    V value;
    Node next;
}

由以上结构的节点依次连接起来所形成的链叫单链表结构

2.双链表的节点结构

Class Node<V>{
    V value;
    Node next;
    Node last;
}

由以上结构的节点依次连接起来所形成的链叫双链表结构

单链表和双链表结构只需要给定一个头部节点head，就可以找到剩下的所有的节点

二、判断一个链表是否为回文结构

【题目】给定一个单链表的头节点head，请判断该链表是否为回文结构。

【例子】1->2->3，返回true；1->2->2->1，返回true；1->2->3，返回false。

【要求】如果链表长度为N，时间复杂度达到O(N)，额外空间复杂度达到O(1)。

思想：

假设有这么一组数，需要判断它是否是回文

（一）解法1：将链表全部节点进栈出栈比较（空间复杂度为O(N)）

解题思路：

1、先将原链表依次进栈（先进后出）

2、再将栈中元素依次出栈

3、每次出栈都与原链表从头节点开始比较，如果比较完都一致，说明是回文链表

代码如下：

/*
 * 第一种思路：需要n个额外空间，将全部节点入栈，再依次出栈与原来节点顺序比较，
 * 看是否是回文
 * */
public static boolean isPalindrome1(Node head) {
    Stack<Node> stack = new Stack<Node>();
    Node cur = head;
    while (cur != null) {   //将所有节点依次放入栈中
        stack.push(cur);  //入栈
        cur = cur.next;
    }
    while (head != null) {  //从头开始遍历
        if (head.value != stack.pop().value) { //每弹出一个节点，跟原节点进行比较
            return false;
        }
        head = head.next;
    }
    return true;
}

（二）解法2：将链表右半部分节点进栈出栈比较（空间复杂度为O(2/N)）

解题思路：（对称思想）

1、先用快慢指针法找到链表中间节点位置

快慢指针概念：

快慢指针中的快慢指的是移动的步长，即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动2，慢指针每次向前移动1次。

2、将中间节点以后的部分放进栈中（右半部分）

3、右半部分出栈，与原链表左半部分依次进行比较，直到栈为空

4、如果比较结果一致，说明是回文链表

代码如下：

/*
 * 第二种思路：需要n/2个额外空间，用快慢指针找到中间节点，将中间节点以后的节点放入栈中，
 * 再出栈同时与原来中间节点以前的另一半部分比较，相同则是回文
 * */
public static boolean isPalindrome2(Node head) {
    if (head == null || head.next == null) {
        return true;
    }
    Node right = head.next;  //right指针最后指向中点右边第一个节点
    Node cur = head;
    while (cur.next != null && cur.next.next != null) {
        right = right.next;
        cur = cur.next.next;
    }
    Stack<Node> stack = new Stack<Node>();
    while (right != null) {  //将右半部分放入栈中
        stack.push(right);
        right = right.next;
    }
    while (!stack.isEmpty()) {  //栈不为空时
        if (head.value != stack.pop().value) {  //栈中弹出来的节点和原链表从头节点开始对比，直到栈弹空
            return false;
        }
        head = head.next;
    }
    return true;
}

（三）解法3：快慢指针+指针逆序解法（空间复杂度为O(1)，符合题目要求）

解题思路：

1、先用快慢指针找到中点位置，我们想让快指针一次走两步，慢指针一次走一步，这样当快指针结束的时候，慢指针刚好来到了中点的位置。

2、将慢指针指向的节点去指向null，再将后面右半部分的指针逆序（为了后面首尾两头往中间靠拢的时候进行比较）

3、链表头尾各用一个引用去记，然后同时往中间遍历，每次走一步，用两边引用指向的进行比较，直到一边为null，则停止，如果比较结果都为true，则说明是回文。注意最后返回结果前将逆序指针恢复原状。

完整代码如下，包含测试用例：

public class IsPalindromeList {
    public static void main(String[] args) {
        Node head = new Node(1);
        Node n1 = new Node(2);
        Node n2 = new Node(3);
        Node n3 = new Node(2);
        Node n4 = new Node(1);
        head.next = n1;
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = null;

        //System.out.println(isPalindrome1(head));  //方法1
        //System.out.println(isPalindrome2(head));  //方法2
        System.out.println(isPalindrome3(head));  //方法3

    }

    public static class Node {
        public int value;
        public Node next;

        public Node(int data) {
            this.value = data;
        }
    }
    
    /*
     * 第三种思路：需要O(1)个额外空间，思路见最上方（推荐使用）
     * 解题思路：
     * 1、先用快慢指针找到中点位置，我们想让快指针一次走两步，慢指针一次走一步，这样当快指针结束的时候，慢指针刚好来到了中点的位置。
     * 2、将慢指针指向的节点去指向null，从中点处往下遍历的时候将后面的指针逆序
     * 3、链表头尾各用一个引用去记，然后同时往中间遍历，每次走一步，直到一边为null，则停止，期间两边引用指向的值相同，则说明是回文。最后返回结果前将逆序指针恢复原状。
     * */
    public static boolean isPalindrome3(Node head) {
        if (head == null || head.next == null) {
            return true;
        }
        Node n1 = head; //慢指针一次走一步
        Node n2 = head; //快指针一次走两步
        while (n2.next != null && n2.next.next != null) { //找到中间节点
            n1 = n1.next;  //n1最终走到中点位置
            n2 = n2.next.next; //n2最终走到结尾
        }
        n2 = n1.next;   //n2指向n1下一个节点，也就是开始逆序
        n1.next = null; //将慢指针的下个节点指向null
        Node n3 = null;
        while (n2 != null) { //右半部分都进行逆序
            n3 = n2.next;  //n3用来保存下一个节点
            n2.next = n1;
            n1 = n2;
            n2 = n3;
        }
        n3 = n1;  //n3 --> 保存最后一个节点
        n2 = head;  //n2 --> 左边第一个节点
        boolean res = true;
        while (n1 != null && n2 != null) {  //检查回文
            if (n1.value != n2.value) {
                res = false;  //结果不一样就是false，否则为true
                break;
            }
            n1 = n1.next;  //n1从左边往中间走
            n2 = n2.next;  //n2从右边往中间走
        }
        n1 = n3.next;
        n3.next = null;
        while (n1 != null) {  //将逆序复原
            n2 = n1.next;
            n1.next = n3;
            n3 = n1;
            n1 = n2;
        }
        return res;
    }
}

第三种方法可以好好钻研一下，面试官看了直呼内行！！！！