深入探索 Java 中的回文（Palindrome）

简介

在编程世界里，回文是一个有趣且广泛应用的概念。在 Java 中，处理回文相关的问题不仅能锻炼逻辑思维，还在字符串处理、算法设计等多个领域有着实际用途。本文将全面深入地探讨 Java 中回文的基础概念、使用方法、常见实践以及最佳实践，帮助读者更好地掌握这一技术点。

回文的基础概念

回文是指一个字符串、数字或其他序列，从前往后读和从后往前读是一样的。例如，字符串 "radar"、"level"，数字 121 等都是回文。在 Java 中，回文的判断主要围绕字符串和数字展开。

Java 中判断回文的使用方法

基于字符串反转

这是一种比较直观的方法。先将字符串反转，然后与原字符串进行比较。如果两者相同，则该字符串是回文。

public class PalindromeExample1 {
    public static boolean isPalindrome(String str) {
        StringBuilder reversed = new StringBuilder(str).reverse();
        return str.equals(reversed.toString());
    }

    public static void main(String[] args) {
        String testStr = "radar";
        if (isPalindrome(testStr)) {
            System.out.println(testStr + " 是回文");
        } else {
            System.out.println(testStr + " 不是回文");
        }
    }
}

双指针法

双指针法更为高效。使用两个指针，一个指向字符串的开头，一个指向字符串的末尾，逐步向中间移动并比较对应字符。

public class PalindromeExample2 {
    public static boolean isPalindrome(String str) {
        int left = 0;
        int right = str.length() - 1;
        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    public static void main(String[] args) {
        String testStr = "level";
        if (isPalindrome(testStr)) {
            System.out.println(testStr + " 是回文");
        } else {
            System.out.println(testStr + " 不是回文");
        }
    }
}

常见实践

判断整数是否为回文

对于整数判断回文，可以先将整数转换为字符串，然后使用上述字符串判断回文的方法。

public class PalindromeIntegerExample {
    public static boolean isPalindrome(int num) {
        String str = String.valueOf(num);
        int left = 0;
        int right = str.length() - 1;
        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    public static void main(String[] args) {
        int testNum = 121;
        if (isPalindrome(testNum)) {
            System.out.println(testNum + " 是回文");
        } else {
            System.out.println(testNum + " 不是回文");
        }
    }
}

判断链表是否为回文

判断链表是否为回文需要一些额外的技巧。可以先找到链表的中间节点，然后反转后半部分链表，最后比较前后两部分。

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class PalindromeLinkedListExample {
    public static boolean isPalindrome(ListNode head) {
        if (head == null) return true;
        ListNode slow = head;
        ListNode fast = head;
        ListNode prev = null;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            ListNode temp = slow.next;
            slow.next = prev;
            prev = slow;
            slow = temp;
        }

        if (fast != null) {
            slow = slow.next;
        }

        while (prev != null && slow != null) {
            if (prev.val != slow.val) {
                return false;
            }
            prev = prev.next;
            slow = slow.next;
        }
        return true;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(2);
        head.next.next.next = new ListNode(1);

        if (isPalindrome(head)) {
            System.out.println("链表是回文");
        } else {
            System.out.println("链表不是回文");
        }
    }
}

最佳实践

性能优化

避免不必要的对象创建：在判断字符串回文时，双指针法避免了创建额外的字符串对象，性能更好。
对于大规模数据，使用更高效的算法：例如在判断链表回文时，采用上述的中间节点和反转后半部分链表的方法，时间复杂度为 O(n)。

代码可读性优化

使用注释：在代码中添加适当的注释，解释关键步骤和算法思路，提高代码的可读性。
方法抽取：将复杂的逻辑抽取成独立的方法，使主方法更加简洁明了。

小结

本文深入探讨了 Java 中回文的相关知识，包括基础概念、判断回文的方法（字符串反转、双指针法）、常见实践（判断整数和链表是否为回文）以及最佳实践（性能和代码可读性优化）。掌握这些知识和技巧，能帮助开发者在处理字符串、数字和链表等数据结构时，更加高效地判断和处理回文问题。

参考资料

《Effective Java》
Oracle Java 官方文档
LeetCode 相关题目及讨论区