解决反转链表后只打印一个节点的问题-java教程-PHP中文网

解决反转链表后只打印一个节点的问题

心靈之曲

发布： 2025-09-28 15:44:13

原创

646人浏览过

解决反转链表后只打印一个节点的问题

在链表操作中，反转链表是一项常见的任务。然而，在实现过程中，开发者可能会遇到一些意想不到的问题，例如反转后链表只打印一个节点。这通常是由于对链表结构理解不透彻导致的。

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

        while (cur != null) {
            System.out.println(cur.data + "    inloop");
            cur = cur.next;
        }

        return true;
    }

    Node reverseList(Node node) {
        Node prev = null;
        Node current = node;
        Node next = null;
        while (current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        node = prev;
        return node;
    }
}

登录后复制

上述代码尝试判断一个链表是否是回文链表。它首先反转链表，然后遍历原始链表并打印每个节点的值。然而，运行结果却只打印了第一个节点。

问题在于，reverseList 方法直接修改了原始链表的结构。反转后，原始链表的头节点变成了尾节点，而尾节点的 next 指针指向 null。因此，当使用 cur = head 遍历原始链表时，循环只执行一次，因为 head.next 已经变成了 null。

以下提供三种解决方案：

1. 创建新的反转链表

最直接的解决方法是在 reverseList 方法中创建一个新的链表，而不是修改原始链表。这样，调用者就可以同时拥有原始链表和反转后的链表，从而可以进行比较操作。

Node reverseList(Node node) {
    Node prev = null;
    Node current = node;
    Node next = null;
    Node newHead = null; // 新链表的头节点

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

        // 创建新节点
        Node newNode = new Node(current.data);
        newNode.next = prev;
        prev = newNode;

        current = next;
    }
    newHead = prev; // 新链表的头节点是prev
    return newHead;
}

登录后复制

在这个修改后的版本中，每次迭代都会创建一个新的节点，并将它添加到新链表的头部。这样，原始链表保持不变，反转后的链表是一个全新的链表。

2. 使用数组辅助判断

AI建筑知识问答

用人工智能ChatGPT帮你解答所有建筑问题

查看详情

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

boolean isPalindrome(Node head) {
    List<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;
}

登录后复制

这种方法简单易懂，但需要额外的 O(n) 空间来存储数组。

3. 反转链表的一半

为了避免额外的空间开销，可以只反转链表的前半部分。然后，将反转后的前半部分与后半部分进行比较。

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;
    }

    // slow 指向中间节点
    Node reversedHalf = reverseList(slow); // 反转后半部分
    Node cur1 = head;
    Node cur2 = reversedHalf;

    while (cur2 != null) {
        if (cur1.data != cur2.data) {
            return false;
        }
        cur1 = cur1.next;
        cur2 = cur2.next;
    }
    return true;
}

登录后复制

这种方法只反转了链表的一半，并且只需要常数级别的额外空间。

总结

在反转链表时，务必注意不要直接修改原始链表的结构，除非这是你的本意。如果需要保留原始链表，请创建新的链表进行反转。此外，还可以考虑使用数组辅助判断或只反转链表的一半等方法来解决问题。选择哪种方法取决于具体的需求和对空间复杂度的要求。理解链表的结构和操作方式是解决此类问题的关键。

以上就是解决反转链表后只打印一个节点的问题的详细内容，更多请关注php中文网其它相关文章！