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

此贴为笔者学习左神算法的记录。

【题目】给定一个链表的头节点 head，请判断该链表是否为回文结构。例如： 1->2->1，返回 true。 1->2->2->1，返回 true。 15->6->15，返回 true。 1->2->3，返回 false。进阶：如果链表长度为 N，时间复杂度达到 O(N)，额外空间复杂度达到 O(1)。

【解答】方法一：方法一是最容易实现的方法，利用栈结构即可。从左到右遍历链表，遍历的过程中把每个节点依次压入栈中。因为栈是先进后出的，所以在遍历完成后，从栈顶到栈底的节点值出现顺序会与原链表从左到右的值出现顺序反过来。那么，如果一个链表是回文结构，逆序之后，值出现的次序还是一样的，如果不是回文结构，顺序就肯定对不上。例如：链表 1->2->3->4，从左到右依次压栈之后，从栈顶到栈底的节点值顺序为 4，3，2，1。两者顺序对不上，所以这个链表不是回文结构。链表 1->2->2->1，从左到右依次压栈之后，从栈顶到栈底的节点值顺序为 1，2，2，1。两者顺序一样，所以这个链表是回文结构。方法一需要一个额外的栈结构，并且需要把所有的节点都压入栈中，所以这个额外的栈结构需要 O(N)的空间。具体过程请参看如下代码中的 isPalindrome1 方法。

    /**
     * 使用栈结构，把链表遍历一遍，同时把链表push到栈中
     * O(N)时间复杂度，O(N）空间复杂度
     * @param head
     * @return
     */
    public boolean isPalindrome1(Node head) {
        // 申请一个栈
        Stack<Node> stack = new Stack<>();

        // 遍历链表，把链表的元素放入栈中
        while (head != null) {
            stack.push(head);
            head = head.next;
        }

        // 把栈中的元素倒出同时比对元素
        while (!stack.isEmpty()) {
            if (head.value != stack.pop().value) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

方法二：方法二对方法一进行了优化，虽然也是利用栈结构，但其实并不需要将所有的节点都压入栈中，只用压入一半的节点即可。首先假设链表的长度为 N，如果 N 是偶数，前 N/2 的节点叫作左半区，后 N/2 的节点叫作右半区。如果 N 是奇数，忽略处于最中间的节点，还是前 N/2 的节点叫作左半区，后 N/2 的节点叫作右半区。例如：

链表 1->2->2->1，左半区为：1，2；右半区为：2，1。链表 1->2->3->2->1，左半区为：1，2；右半区为：2，1。方法二就是把整个链表的右半部分压入栈中，压入完成后，再检查栈顶到栈底值出现的顺序是否和链表左半部分的值相对应。例如：链表 1->2->2->1，链表的右半部分压入栈中后，从栈顶到栈底为 1，2。链表的左半部分也是 1，2。所以这个链表是回文结构。链表 1->2->3->2->1，链表的右半部分压入栈中后，从栈顶到栈底为 1，2。链表的左半部分也是 1，2。所以这个链表是回文结构。链表 1->2->3->3->1，链表的右半部分压入栈中后，从栈顶到栈底为 1，3。链表的左半部分也是 1，2。所以这个链表不是回文结构。方法二可以直观地理解为将链表的右半部分“折过去”，然后让它和左半部分比较，如图2-5 所示。

方法二的具体过程请参看如下代码中的 isPalindrome2 方法。

    public boolean isPalindrome2(Node head) {
        // 慢指针
        Node right = head.next;
        // 快指针
        Node cur = head;

        /**
         * 快慢指针：
         * 快指针和慢指针都从头节点出发，慢指针一次走一步，快指针一次走两步
         * 如果链表长度是偶数：慢指针将来到中间两个节点的左边那个节点
         * 如果链表长度是奇数：慢指针将来到中间节点左侧的那个节点
         * 快指针从头节点出发，慢指针从第二个节点出发，慢指针一次走一步，快指针一次走两步
         * 如果链表长度是偶数：慢指针将来到中间两个节点的右边那个节点
         * 如果链表长度是奇数：慢指针将来到中间节点右侧的那个节点
         */
        while (cur.next != null && cur.next.next != null) {
            // 慢指针最终来到中间节点的右边一个位置
            right = right.next;
            cur = cur.next.next;
        }
        Stack<Node> stack = new Stack<>();
        while (right != null) {
            // 把链表右半部分放入栈中
            stack.push(right);
        }

        // 将栈中元素一个一个弹出，和链表左半部分比较
        while (!stack.isEmpty()) {
            if (head.value != stack.pop().value) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

方法三：方法三不需要栈和其他数据结构，只用有限几个变量，其额外空间复杂度为 O(1)，就可以在时间复杂度为 O(N)内完成所有的过程，也就是满足进阶的要求。具体过程如下： 1．改变链表右半区的结构，使整个右半区反转，最后指向中间节点。例如：链表 1->2->3->2->1，通过这一步将其调整之后的结构如图 2-6 所示。链表 1->2->3->3->2->1，将其调整之后的结构如图 2-7 所示。

我们将左半区的第一个节点（也就是原链表的头节点）记为 leftStart，右半区反转之后最右边的节点（也就是原链表的最后一个节点）记为 rightStart。 2．leftStart 和 rightStart 同时向中间点移动，移动每一步时都比较 leftStart 和 rightStart 节点的值，看是否一样。如果都一样，说明链表为回文结构，否则不是回文结构。 3．不管最后返回的是 true 还是 false，在返回前都应该把链表恢复成原来的样子。 4．链表恢复成原来的结构之后，返回检查结果。粗看起来，虽然方法三的整个过程也没有多少难度，但要想用有限几个变量完成以上所有的操作，在实现上还是比较考查代码实现能力的。方法三的全部过程请参看如下代码中的isPalindrome3 方法，该方法只申请了三个 Node 类型的变量。

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

全站热榜