判断链表是否回文

判断链表是否回文

题目：给出链表头结点，判断链表是否是回文结构

    
    public static class Node {

        public int value;

        public Node next;

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

方法1：借助Stack将整条链表压入栈中，然后从Stack中pop出元素和链表每一个元素逐个去做比较。时间复杂度为O(N)，空间复杂度为O(N)。代码如下：

    
    public static boolean isPalindrome(Node head) {
        Stack stack = new Stack<>();
        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(N)，空间复杂度O(N)，但是相比方法1，省了一点空间。代码如下：

 
    public static boolean isPalindrome(Node head) {
        if (head == null || head.next == null) { //链表的长度小于或等于1,那么一定是回文结构
            return true;
        }
        //slow指针,起始位置是2
        Node right = head.next;

        //fast指针,起始位置是1
        Node cur = head;

        while (cur.next != null && cur.next.next != null) { //保证fast指针每走2步,slow指针走1步
            right = right.next;
            cur = cur.next.next;
        }

        //此时right就是右部分的第一个节点
        Stack stack = new Stack<>();

        //将右部分的所有Node节点加入栈中
        while (right != null) {
            stack.push(right);
            right = right.next;
        }

        //将栈中元素d出,并与左部分Node节点逐一比对
        while (!stack.isEmpty()) {
            if (head.value != stack.pop().value) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

方法3：将链表分为左右部分。将右部分进行反转。若链表为 a->b->c->d ，左边部分为a->b，右边部分为c->d，那么反转后就是a->b<-c<-d。那么右边部分从d开始，左边部分从a开始，两个都往中间靠拢去比对。最后，恢复链表，返回结果。代码如下：

  
    public static boolean isPalindrome(Node head) {
        if (head == null || head.next == null) { //链表的长度小于或等于1
            return true;
        }
        //链表的长度大于1
        Node fast = head;
        Node slow = head;
        while (fast.next != null && fast.next.next != null) { //快指针每次走2步,慢指针每次走1步
            slow = slow.next;
            fast = fast.next.next;
        }
        //此时slow来到了上面例子的c点或b点
        Node rightPartNode = slow.next; //右部分第一个Node节点
        slow.next = null;  //断开左右部分的联系
        Node next = null;
        //反转链表
        while (rightPartNode != null) {
            next = rightPartNode.next;
            rightPartNode.next = slow;
            slow = rightPartNode;
            rightPartNode = next;
        }
        Node rightPartLastNode = slow; //此时的slow是右部分的最后一个元素 让rightPartLastNode也指向slow位置
        Node leftPartFirstNode = head; //leftPartFirstNode 用于保存左边第一个元素
        boolean res = true;
        while (rightPartLastNode != null && leftPartFirstNode != null) { //当且仅当来到y点时,退出循环,因为y点的next指针前面断了
            if (rightPartLastNode.value != leftPartFirstNode.value) {
                res = false;
                break;
            }
            rightPartLastNode = rightPartLastNode.next; //向左靠近y点
            leftPartFirstNode = leftPartFirstNode.next;  //向右靠近y点
        }
        //恢复链表
        //此时slow是右部分链表的最右边的元素
        Node cur = slow.next;
        slow.next = null;
        next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = slow;
            slow = cur;
            cur = next;
        }
        return res;
    }

最后，伟子哥的小迷弟来句总结：

方法1和方法2均需要借助栈的数据结构，空间复杂度为O(N)。方法3在保证时间复杂度为O(N)的情况下，空间复杂度为O(1)。当然，方法3的代码也是最复杂的。当然我是希望面试和笔试场上，若空间复杂度没有要求的话，我个人推荐写第一种，毕竟很简单嘛。若要求空间复杂度为O(1)，那没办法，只能平时多下功夫，把方法3看懂，练熟。数据结构和算法不仅仅是靠想，还要多动手去code。 Stay hungry stay foolish.