Palindrome Linked List in Java

2025 年 5 月 3 日 | 阅读 10 分钟

回文链表是指其元素序列从前向后读与从后向前读相同的链表。要确定一个链表是否是回文链表，我们需要在保持结构不变的情况下，比较链表的前半部分和反转后的后半部分。

回文链表示例

输入：链表：1 -> 2 -> 3 -> 2 -> 1

输出：链表是否为回文？ True

解释

链表 1 -> 2 -> 3 -> 2 -> 1 是回文链表，因为其序列从前向后读与从后向前读相同。通过反转后半部分（2 -> 1 变为 1 -> 2），它与前半部分（1 -> 2 -> 3）匹配，证实了该链表是回文链表。

方法 1：使用双指针技术

算法

步骤 1：检查链表是否为空或只有一个节点： 如果链表为空 (head == null) 或只有一个元素 (head.next == null)，则它本身就是回文链表。函数立即返回 true。

步骤 2：找到链表中点： 使用两个指针：慢指针和快指针。慢指针一次移动一个节点，而快指针一次移动两个节点。当快指针到达链表末尾时，慢指针将位于链表中点。

步骤 3：反转链表的后半部分： 一旦慢指针到达中点，链表的后半部分（从慢指针开始）将被反转。这通过遍历后半部分并更改每个节点的 next 指针以指向其前一个节点来实现。完成此步骤后，链表的后半部分将被反转，并且慢指针将指向此反转后的后半部分链表的头部。

步骤 4：比较链表的两个部分： 现在，比较链表的前半部分（从头部开始）和反转后的后半部分（从慢指针开始）。

步骤 4.1：将两个指针移向各自部分末尾： 反转链表后半部分后，您现在有两个指针：一个从链表头部（前半部分）开始，另一个从反转后的后半部分头部（慢指针所在位置）开始。

步骤 5：使用两个指针： 一个从链表头部开始，另一个从反转后的后半部分开始。遍历两个部分，比较每个节点的数值。如果发现任何不匹配，则返回 false（表示链表不是回文）。如果所有数值都匹配，则返回 true（表示链表是回文）。

步骤 6：结论： 如果在比较过程中没有发现任何不匹配，则该链表是回文链表。

让我们使用 Java 程序实现上述算法。

文件名：PalindromeLinkedList.java

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
public class PalindromeLinkedList {
public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;
// Step 1: Find the middle of the linked list
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
// Step 2: Reverse the second half of the list
        ListNode prev = null, curr = slow;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
// Step 3: Compare the two halves
        ListNode firstHalf = head, secondHalf = prev;
        while (secondHalf != null) {
            if (firstHalf.val != secondHalf.val) return false;
            firstHalf = firstHalf.next;
            secondHalf = secondHalf.next;
        }
return true;
    }
    public static void main(String[] args) {
        // Create a linked list: 1 -> 2 -> 3 -> 2 -> 1
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(2);
        head.next.next.next.next = new ListNode(1);
PalindromeLinkedList palindromeLinkedList = new PalindromeLinkedList();
        boolean result = palindromeLinkedList.isPalindrome(head);
// Print the result
        System.out.println("Is the linked list a palindrome? " + result);
    }
}   

输出

 
Is the linked list a palindrome? true

复杂度分析

时间复杂度

此算法的时间复杂度为 O(n)，因为我们遍历链表两次：一次找到中点，一次比较两个部分。反转后半部分也需要 O(n)。由于没有使用额外的空间，因此复杂度为 O(1)。

空间复杂度

此算法的空间复杂度为 O(1)，因为它只使用了常数级别的额外空间。它依赖于几个指针变量来遍历和操作链表，但没有使用任何额外数据结构或数组，使其空间效率高。

方法 2：使用栈

算法

步骤 1：处理边缘情况： 如果链表为空 (head 为 null) 或只有一个节点 (head.next 为 null)，我们可以立即得出结论，它是一个回文链表。单个元素或空列表正反读都相同，因此返回 true。

步骤 2：初始化两个指针： 我们使用两个指针，慢指针和快指针。两者都从链表头部开始。慢指针一次移动一个节点，而快指针一次移动两个节点。速度上的差异使我们能够找到链表中点。当快指针到达链表末尾时，慢指针将位于中点。这是因为快指针的移动速度是慢指针的两倍。

步骤 3：将链表前半部分压入堆栈： 随着慢指针沿着链表移动，我们将当前节点的值压入堆栈。堆栈遵循“后进先出”(LIFO) 原则，这意味着链表前半部分的值将按反向顺序存储。跳过中间元素（如果链表长度为奇数）

步骤 3.1： 如果链表包含奇数个元素，当慢指针到达中点时，快指针将不为 null。在这种情况下，我们将慢指针向前移动一步以跳过中间元素。此步骤确保我们只比较链表的后半部分与存储在堆栈中的前半部分。

步骤 4：将链表后半部分与堆栈进行比较： 现在，慢指针位于链表后半部分的开头。我们开始将此后半部分的每个节点与从堆栈中弹出的值进行比较。对于后半部分的每个节点，我们从堆栈中弹出一个值，并检查它是否与当前节点的值匹配。如果任何时候值不匹配，我们将返回 false，因为链表不是回文。

步骤 5：返回结果： 如果我们到达后半部分的末尾，并且后半部分的所有值都与从堆栈中弹出的值匹配，我们就得出结论，该链表是回文链表，并返回 true。

让我们使用 Java 程序实现上述算法。

文件名：PalindromeLinkedList.java

import java.util.Stack;
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
public class PalindromeLinkedList {
// Function to check if the linked list is a palindrome using a stack
    public boolean isPalindrome(ListNode head) {
        // Step 1: Edge case: If the list is empty or contains only one element
        if (head == null || head.next == null) {
            return true;
        }
// Step 2: Use slow and fast pointers to find the middle of the list
        ListNode slow = head, fast = head;
   // Use a stack to store the first half of the list
        Stack<Integer> stack = new Stack<>();
        // Traverse the list and push the first half onto the stack
        while (fast != null && fast.next != null) {
            stack.push(slow.val);
            slow = slow.next;
            fast = fast.next.next;
        }
     // Step 3: If the list has an odd number of elements, skip the middle element
        if (fast != null) {
            slow = slow.next;
        }
        // Step 4: Compare the second half with the stack
while (slow != null) {
            if (stack.pop() != slow.val) {
                return false; // Mismatch found
            }
            slow = slow.next;
        }
return true; // All values matched
    }
public static void main(String[] args) {
        // Create a linked list: 1 -> 2 -> 3 -> 2 -> 1
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(2);
        head.next.next.next.next = new ListNode(1);
PalindromeLinkedList palindromeLinkedList = new PalindromeLinkedList();
        boolean result = palindromeLinkedList.isPalindrome(head);
       // Print the result
        System.out.println("Is the linked list a palindrome? " + result);
    }
}   

输出

 
Is the linked list a palindrome? true

复杂度分析

时间复杂度

此算法的时间复杂度为 O(n)，其中 n 是链表中的节点数。我们遍历链表两次：一次将前半部分压入堆栈，一次将后半部分与堆栈进行比较，这两者都需要线性时间。

空间复杂度

此算法的空间复杂度为 O(n)，其中 n 是链表中的节点数。这是因为使用了堆栈来存储链表前半部分的元素以进行比较。除了堆栈外，不需要额外的数据结构。

方法 3：使用递归

算法

步骤 1：设置递归： 使用递归的思想是从头部遍历链表直到尾部，并在递归展开时比较开始和结束的节点。递归函数将遍历链表并回溯以检查对称性，而无需显式反转链表。

步骤 2：初始化：frontPointer： 初始化一个指针 (frontPointer) 指向链表头部。在递归回溯期间，它将跟踪来自前方的当前节点。我们通过调用 recursivelyCheck(head) 来初始化递归，其中 head 是链表的起始节点。

步骤 3：基本情况（递归结束条件）： 在任何递归函数中，都需要一个基本情况来停止进一步的递归调用。对于回文检查，基本情况是到达链表末尾。条件：当当前节点为 null 时，表示我们已到达链表末尾。此时，我们返回 true，因为我们尚未遇到任何不匹配。

步骤 4：递归步骤（遍历到末尾）： 随着我们递归地调用 recursivelyCheck(current.next)，函数会逐个节点向前移动链表，直到到达末尾。递归继续而不检查回文属性；它只关心到达基本情况。

步骤 5：回溯和比较： 在递归开始展开后（即到达基本情况），我们开始比较节点。关键思想是将当前节点的值与由 frontPointer 跟踪的列表前面的值进行比较。

步骤 6：比较： 在每次回溯级别，我们将当前节点的值与 frontPointer 指向的节点的值进行比较。如果值不匹配，我们将立即返回 false，因为链表不是回文。

步骤 7：最终检查： 如果递归函数完成了所有比较并且节点继续匹配，则函数将返回 true，表示链表是回文链表。如果在任何时候发现不匹配，递归将立即返回 false，并且链表将被视为非回文链表。

步骤 8：函数返回值： 链表是否为回文的最终结果将返回给开始检查的主函数。结果取决于从前面和后面的所有节点对是否匹配。

让我们使用 Java 程序实现上述算法。

文件名：PalindromeLinkedList.java

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
public class PalindromeLinkedList {
    private ListNode frontPointer; // To keep track of the head for comparison
public boolean isPalindrome(ListNode head) {
        frontPointer = head; // Initialize the front pointer to head
        return recursivelyCheck(head); // Start the recursion
    }
private boolean recursivelyCheck(ListNode current) {
        if (current == null) {
            return true; // Base case: if the end of the list is reached
        }
// Recursively check the rest of the list
        boolean isPalindromeRest = recursivelyCheck(current.next);
// Compare the current node's value with the front pointer
        if (!isPalindromeRest || frontPointer.val != current.val) {
            return false;
        }
// Move the front pointer forward
        frontPointer = frontPointer.next;
return true;
    }
public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(2);
        head.next.next.next.next = new ListNode(1);
palindromeLinkedList palindromeLinkedList = new PalindromeLinkedList();
        boolean result = palindromeLinkedList.isPalindrome(head);
        System.out.println("Is the linked list a palindrome? " + result);
    }
}   

输出

 
Is the linked list a palindrome? true

复杂度分析

时间复杂度

递归回文检查的时间复杂度为 O(n)，其中 n 是链表中的节点数。递归期间每个节点都会被访问一次，并且在递归展开的每一步都会进行当前节点与 frontPointer 之间的比较。

空间复杂度

递归回文检查的空间复杂度为 O(n)，这是因为使用了用于递归的调用堆栈。每个递归调用都会向堆栈添加一个新帧，在最坏的情况下，递归深度与链表中的节点数成正比。

下一个主题Java 中的截断是什么

← 上一个下一个 →

Palindrome Linked List in Java

回文链表示例

方法 1：使用双指针技术

算法

复杂度分析

时间复杂度

方法 2：使用栈

算法

复杂度分析

时间复杂度

空间复杂度

方法 3：使用递归

算法

复杂度分析

时间复杂度

空间复杂度

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Palindrome Linked List in Java

回文链表示例

方法 1：使用双指针技术

算法

复杂度分析

时间复杂度

方法 2：使用栈

算法

复杂度分析

时间复杂度

空间复杂度

方法 3：使用递归

算法

复杂度分析

时间复杂度

空间复杂度

相关帖子

实现 Java Queue 接口

Java 中的 Ganesha 图案

Abstract Method in Java

Java 中的 final 类

Java 中的 503 错误处理重试代码片段

Java 中的 mapToInt()

如何在 Java 中将数组传递给函数

Java Object getClass() Method

How to Sort an Array in Java

Java 中的火星探测器问题

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器