反转链表后只输出一个节点的问题分析与解决-java教程-PHP中文网

反转链表后只输出一个节点的问题分析与解决

花韻仙語

发布： 2025-09-28 15:58:15

原创

430人浏览过

反转链表后只输出一个节点的问题分析与解决

本文旨在解决反转链表后只输出一个节点的问题。通过分析问题代码，明确了反转链表导致原链表结构改变的原因。文章提供了三种解决方案：创建新链表、使用数组存储链表值、以及仅反转链表的一半，并对每种方法进行了详细的讲解，帮助读者理解和掌握链表反转的正确方法，避免类似问题的发生。

在链表操作中，反转链表是一个常见的操作。然而，不当的反转操作可能会导致一些意想不到的问题，例如只输出一个节点。本文将深入分析这个问题，并提供多种解决方案。

问题分析

问题代码的关键在于reverseList函数。这个函数直接修改了原链表的next指针，导致原链表的结构发生了改变。具体来说，在反转链表后，原链表的头节点变成了反转后链表的尾节点，其next指针指向了null。因此，在isPalindrome函数中，当head指向原链表的头节点（现在是反转后的尾节点）时，while(cur!=null)循环只会执行一次，导致只输出一个节点。

解决方案

为了解决这个问题，我们可以采用以下三种方法：

1. 创建新的反转链表

这种方法的核心思想是在反转链表时，创建一个新的链表，而不是修改原链表。这样，我们就可以同时拥有原链表和反转后的链表，从而方便地进行比较。

class Solution {
    //Function to check whether the list is palindrome.
    boolean isPalindrome(Node head) {
        Node reversed = reverseList(head);
        Node cur = head;
        Node curReversed = reversed;

        while(cur!=null && curReversed != null) {
            if(cur.data != curReversed.data){
                return false;
            }
            cur=cur.next;
            curReversed = curReversed.next;
        }

        return true;
    }

    Node reverseList(Node head) {
        Node prev = null;
        Node current = head;
        Node next = null;
        Node newHead = null;

        while (current != null) {
            next = current.next;

            Node newNode = new Node(current.data); // Create a new node
            newNode.next = prev;
            prev = newNode;

            current = next;

        }
        newHead = prev;
        return newHead;
    }
}

class Node {
    int data;
    Node next;
    Node(int d) {
        data = d;
        next = null;
    }
}

登录后复制

注意事项：

飞书多维表格

表格形态的AI工作流搭建工具，支持批量化的AI创作与分析任务，接入DeepSeek R1满血版

查看详情

这种方法需要额外的空间来存储新的链表，空间复杂度为O(n)。
在创建新节点时，需要复制原节点的数据，确保新链表和原链表的数据一致。

2. 使用数组存储链表值

这种方法将链表中的所有节点的值存储到一个数组中，然后判断数组是否是回文的。

import java.util.ArrayList;

class Solution {
    //Function to check whether the list is palindrome.
    boolean isPalindrome(Node head) {
        ArrayList<Integer> list = new ArrayList<>();
        Node cur = head;
        while (cur != null) {
            list.add(cur.data);
            cur = cur.next;
        }

        int left = 0;
        int right = list.size() - 1;
        while (left < right) {
            if (!list.get(left).equals(list.get(right))) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

class Node {
    int data;
    Node next;
    Node(int d) {
        data = d;
        next = null;
    }
}

登录后复制

注意事项：

这种方法也需要额外的空间来存储数组，空间复杂度为O(n)。
这种方法适用于链表长度较小的情况。如果链表长度很大，可能会导致内存溢出。

3. 反转链表的一半

这种方法只反转链表的前一半，然后将反转后的前半部分和后半部分进行比较。

class Solution {
    //Function to check whether the list is palindrome.
    boolean isPalindrome(Node head) {
        if (head == null || head.next == null) {
            return true;
        }

        Node slow = head;
        Node fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // Reverse the second half
        Node prev = null;
        Node current = slow;
        Node next = null;
        while (current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }

        // Compare the first half and the reversed second half
        Node firstHalf = head;
        Node secondHalf = prev;
        while (secondHalf != null) {
            if (firstHalf.data != secondHalf.data) {
                return false;
            }
            firstHalf = firstHalf.next;
            secondHalf = secondHalf.next;
        }

        return true;
    }
}

class Node {
    int data;
    Node next;
    Node(int d) {
        data = d;
        next = null;
    }
}

登录后复制

注意事项：