小学生都能懂的题解 | #判断一个链表是否为回文结构#

问题描述

假设你有一串珠子，每颗珠子上都有一个数字。我们要检查这串珠子上的数字是不是回文结构。回文的意思就是，无论你从前往后读还是从后往前读，这些数字都是一样的。

解决方法

我们可以用几个步骤来检查这串珠子是否是回文的：

1. 找到中间的珠子

我们先找到这串珠子的中间位置。就像你有一条绳子，我们要找到它的中心点。我们可以用两只手来帮忙找：

• 一只手每次移动一颗珠子（慢手）。
• 另一只手每次移动两颗珠子（快手）。
• 当快手无法再移动时，慢手就在中间位置了。

2. 把后面的珠子反过来

找到中间位置后，我们把后面的珠子反过来，就像把一条项链的后半部分反过来一样。

3. 比较前后两部分

然后，我们比较前面的珠子和反过来的后面珠子，看看它们的数字是否一一对应相等。

具体步骤

假设你有这样一串珠子：1, 2, 2, 1。

1. 找到中间点：
1. 我们发现中间点是 2。
2. 把后面的珠子反过来：
1. 变成 1, 2, 2 和 1。
3. 比较前后两部分：
1. 第一颗珠子：1 和 1 相等。
2. 第二颗珠子：2 和 2 相等。所有的珠子都相等，所以这串珠子是回文的！

示例

示例1

输入：{1}

• 中间点就是 1。
• 反转后的链表：1。
• 比较：1 和 1 相等。
• 结论：是回文。

示例2

输入：{2, 1}

• 中间点是 1。
• 反转后的链表：2 和 1。
• 比较：2 和 1 不相等。
• 结论：不是回文。

示例3

输入：{1, 2, 2, 1}

• 中间点是 2。
• 反转后的链表：1, 2, 2 和 1。
• 比较：1 和 1 相等，2 和 2 相等。
• 结论：是回文。

代码实现

下面是一个简单的 Java 实现：

public class Solution {

    // 检查链表是否为回文
    public boolean isPalindrome(ListNode head) {
        // 如果链表为空或只有一个节点，它是回文
        if (head == null || head.next == null) {
            return true;
        }

        // 找到中间节点
        ListNode middle = findMiddle(head);
        ListNode secondHalf = reverse(middle);

        // 比较前半部分和反转后的后半部分
        ListNode firstHalf = head;
        while (secondHalf != null) {
            if (firstHalf.val != secondHalf.val) {
                return false; // 数字不同，不是回文
            }
            firstHalf = firstHalf.next;
            secondHalf = secondHalf.next;
        }

        return true; // 所有数字相同，是回文
    }

    // 寻找中间节点
    private ListNode findMiddle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next; // 慢指针
            fast = fast.next.next; // 快指针
        }

        return slow;
    }

    // 反转链表
    private ListNode reverse(ListNode head) {
        ListNode previous = null;
        ListNode current = head;

        while (current != null) {
            ListNode next = current.next;
            current.next = previous;
            previous = current;
            current = next;
        }

        return previous;
    }
}

如果这篇文章帮到你，请点个免费的👍，让它帮助更多的人。