链表训练5：三种方法带你优雅判断回文链表

链表专题 0 484

【题目描述】

给定一个链表的头节点 head, 请判断该链表是否为回文结构。

例如：

1->2->1，返回 true.

1->2->2->1, 返回 true。

1->2->3，返回 false。

【要求】

如果链表的长度为 N, 时间复杂度达到 O(N)。

【解答】

方法1

我们可以利用栈来做辅助，把链表的节点全部入栈，在一个一个出栈与链表进行对比，例如对于链表 1->2->3->2->2，入栈后如图:

然后再逐一出栈与链表元素对比。

这种解法比较简单，时间复杂度为 O(n), 空间复杂度为 O(n)。

代码如下

    //方法1
    public static boolean f1(Node head) {
        if (head == null || head.next == null) {
            return true;
        }
        Node temp = head;
        Stack stack = new Stack<>();
        while (temp != null) {
            stack.push(temp);
            temp = temp.next;
        }
        while (!stack.isEmpty()) {
            Node t = stack.pop();
            if (t.value != head.value) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

方法二

真的需要全部入栈吗？其实我们也可以让链表的后半部分入栈就可以了，然后把栈中的元素与链表的前半部分对比，例如 1->2->3->2->2 后半部分入栈后如图：

然后逐个出栈，与链表的前半部分(1->2)对比。这样做的话空间复杂度会减少一半。

代码如下：

    //方法2
    public static boolean f(Node head) {
        if(head == null || head.next == null)
            return true;
        Node slow = head;//慢指针
        Node fast = head;//快指针
        Stack stack = new Stack<>();
        //slow最终指向中间节点
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        System.out.println(slow.value);
        slow = slow.next;
        while (slow != null) {
            stack.push(slow);
            slow = slow.next;
        }
        //进行判断
        while (!stack.isEmpty()) {
            Node temp = stack.pop();
            if (head.value != temp.value) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

方法三：空间复杂度为 O(1)。

上道题我们有作过链表的反转的，没看过的可以看一下勒：【链表问题】如何优雅着反转单链表]，我们可以把链表的后半部分进行反转，然后再用后半部分与前半部分进行比较就可以了。这种做法额外空间复杂度只需要 O(1), 时间复杂度为 O(n)。

代码如下:

    //方法3
    public static boolean f2(Node head) {
        if(head == null || head.next == null)
            return true;
        Node slow = head;//慢指针
        Node fast = head;//快指针
        //slow最终指向中间节点
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        Node revHead = reverse(slow.next);//反转后半部分
        //进行比较
        while (revHead != null) {
            System.out.println(revHead.value);
            if (revHead.value != head.value) {
                return false;
            }
            head = head.next;
            revHead = revHead.next;
        }
        return true;
    }
    //反转链表
    private static Node reverse(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node newHead = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

这道题被问的概率也是挺高的，就算代码写不出，也得至少知道思路

问题拓展

思考：如果给你的是一个环形链表，并且指定了头节点，那么该如何判断是否为回文链表呢？

如果喜欢本网站{https://www.iamshuaidi.com), 那么可以把该网站分享给其他人，帅地正在疯狂更新中….

链表

【题目描述】

【要求】

【解答】

问题拓展

发表评论 取消回复

发表评论取消回复