数据结构与算法-- 回文链表（非常全的解法）

题目描述 请判断一个链表是否为回文链表。

示例1:

输入: 1->2 输出: false 示例2:

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

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

首先是节点的定义：

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

        public Node(int data){
            this.value = data;
        }
    }

方法一

• 该方法适合于在笔试机试中使用。原理很简单，就是利用一个辅助栈把数据装进去，这样在pop()的时候就是原先的顺序的倒叙输出。空间复杂度O(N)

    //空间复杂度O(N)
    //1.方法一：利用一个栈的后进先出的性质来存储
    public static boolean isPalindrome1(Node head){
        Stack<Node> stack = new Stack<>();
        Node cur = head;
        while (cur!=null){
            stack.push(cur);
            cur = cur.next;
        }
        while (!stack.isEmpty()){
            cur = stack.pop();
            if(cur.value != head.value){
                return false;
            }
            head = head.next;
        }
        return true;
    }

方法二

• 利用快慢指针，一个一次走两步，一个一次走一步，快指针到头后，慢指针在链表的中间位置。然后从中间位置开始用一个栈开始存储，这时候只需要O(N/2)的空间复杂度。

//空间复杂度O(N/2)
    //利用一个快慢指针，快指针一次走两步，慢指针一次走一步
    //快指针走到头后，慢指针走到链表的中间位置
    //然后用一个辅助栈存储后半部分
    public static boolean isPalindrome2(Node head){
        if(head == null || head.next == null){
            return true;
        }
        Node slow = head.next;
        Node fast = head;

        while (slow.next!=null && slow.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        Stack<Node> stack = new Stack<>();
        while (slow != null){
            stack.push(slow);
            slow = slow.next;
        }
        while (!stack.isEmpty()){
            if(head.value != stack.pop().value){
                return false;
            }
            head = head.next;
        }
        return true;
    }

方法三

• 这个方法不需要额外的空间，空间复杂度为O(1)，思路还是利用两个快慢指针，其中快指针走到头，慢指针走到中间，这里面也涉及到指针个数的奇数偶数问题如果奇数那就是中间，偶数的话要控制在中间的后面那个开始。然后开始反转右边的链表，其中中间节点的next指向null， 最后的结果也就是左边的一次指向中间节点，右侧的一次指向中间节点，然后从两侧开始遍历，看值是否相同，最后再把右侧的链表反转回去，恢复到初始状态。

//空间复杂度O(1)
    public static boolean isPalindrome3(Node head){
        if(head == null || head.next == null){
            return true;
        }
        Node fast = head;
        Node slow = head;

        while (fast.next!=null && fast.next.next!=null){// find mid node
            fast = fast.next.next; // slow -> mid
            slow = slow.next; // fast -> end
        }
        fast = slow.next; // fast -> 右边部分的第一个节点
        slow.next = null;  // mid.next -> null
        Node n = null;
        while (fast != null){ // 右边部分反转
            n = fast.next; // n -> 保存下一个节点
            fast.next = slow;
            slow = fast; // 继续向下运行
            fast = n; // 继续向下运行
        }
        n = slow; // n -> 最后一个节点
        fast = head; // 左边的第一个节点
        boolean res = true;
        while (slow != null && fast != null){
            if(slow.value != fast.value){
                res = false;
                break;
            }
            slow = slow.next;
            fast = fast.next;
        }
        slow = n.next;
        n.next = null;
        while (slow != null){
            fast = slow.next;
            slow.next = n;
            n = slow;
            slow = fast;
        }
        return res;
    }
    public static void printLinkedList(Node node) {
        System.out.print("Linked List: ");
        while (node != null) {
            System.out.print(node.value + " ");
            node = node.next;
        }
        System.out.println();
    }

• 最后的全部代码加上主函数测试：

import java.util.Stack;

/**
 * 测试链表是否是回文链表
 * @author zhx
 */
public class IsPalindromeList {


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

        public Node(int data){
            this.value = data;
        }

    }
    //空间复杂度O(N)
    //1.方法一：利用一个栈的后进先出的性质来存储
    public static boolean isPalindrome1(Node head){
        Stack<Node> stack = new Stack<>();
        Node cur = head;
        while (cur!=null){
            stack.push(cur);
            cur = cur.next;
        }
        while (!stack.isEmpty()){
            cur = stack.pop();
            if(cur.value != head.value){
                return false;
            }
            head = head.next;
        }
        return true;
    }

    //空间复杂度O(N/2)
    //利用一个快慢指针，快指针一次走两步，慢指针一次走一步
    //快指针走到头后，慢指针走到链表的中间位置
    //然后用一个辅助栈存储后半部分
    public static boolean isPalindrome2(Node head){
        if(head == null || head.next == null){
            return true;
        }
        Node slow = head.next;
        Node fast = head;

        while (slow.next!=null && slow.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        Stack<Node> stack = new Stack<>();
        while (slow != null){
            stack.push(slow);
            slow = slow.next;
        }
        while (!stack.isEmpty()){
            if(head.value != stack.pop().value){
                return false;
            }
            head = head.next;
        }
        return true;
    }

    //空间复杂度O(1)
    public static boolean isPalindrome3(Node head){
        if(head == null || head.next == null){
            return true;
        }
        Node fast = head;
        Node slow = head;

        while (fast.next!=null && fast.next.next!=null){// find mid node
            fast = fast.next.next; // slow -> mid
            slow = slow.next; // fast -> end
        }
        fast = slow.next; // fast -> 右边部分的第一个节点
        slow.next = null;  // mid.next -> null
        Node n = null;
        while (fast != null){ // 右边部分反转
            n = fast.next; // n -> 保存下一个节点
            fast.next = slow;
            slow = fast; // 继续向下运行
            fast = n; // 继续向下运行
        }
        n = slow; // n -> 最后一个节点
        fast = head; // 左边的第一个节点
        boolean res = true;
        while (slow != null && fast != null){
            if(slow.value != fast.value){
                res = false;
                break;
            }
            slow = slow.next;
            fast = fast.next;
        }
        slow = n.next;
        n.next = null;
        while (slow != null){
            fast = slow.next;
            slow.next = n;
            n = slow;
            slow = fast;
        }
        return res;
    }
    public static void printLinkedList(Node node) {
        System.out.print("Linked List: ");
        while (node != null) {
            System.out.print(node.value + " ");
            node = node.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Node head = null;
        printLinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.print(isPalindrome2(head) + " | ");
        System.out.println(isPalindrome3(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        printLinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.print(isPalindrome2(head) + " | ");
        System.out.println(isPalindrome3(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        printLinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.print(isPalindrome2(head) + " | ");
        System.out.println(isPalindrome3(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(1);
        printLinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.print(isPalindrome2(head) + " | ");
        System.out.println(isPalindrome3(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        printLinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.print(isPalindrome2(head) + " | ");
        System.out.println(isPalindrome3(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(1);
        printLinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.print(isPalindrome2(head) + " | ");
        System.out.println(isPalindrome3(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(1);
        printLinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.print(isPalindrome2(head) + " | ");
        System.out.println(isPalindrome3(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(2);
        head.next.next.next = new Node(1);
        printLinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.print(isPalindrome2(head) + " | ");
        System.out.println(isPalindrome3(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(2);
        head.next.next.next.next = new Node(1);
        printLinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.print(isPalindrome2(head) + " | ");
        System.out.println(isPalindrome3(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");
    }
}