反转链表后仅打印一个节点的问题分析与解决_技术教程

在链表操作中，反转链表是一个常见的操作。然而，不当的反转链表操作可能会导致一些意想不到的问题，例如，反转链表后仅打印一个节点。理解反转链表对原链表的影响至关重要。

问题分析

问题代码中，reverseList 函数用于反转链表。关键在于理解反转链表后，原链表的结构发生了变化。具体来说，原链表的头节点变成了反转后的尾节点，其 next 指针指向 null。因此，在反转链表后，如果直接使用原链表的头节点进行遍历，由于其 next 指针为 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);
            newNode.next = prev;
            prev = newNode;

            current = next;
        }
        newHead = prev; // 反转后的头节点
        return newHead;
    }
}

优点： 简单易懂，不会修改原链表。

缺点： 需要额外的空间来存储新的链表，空间复杂度为 O(n)。

2. 使用数组存储链表值

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

import java.util.ArrayList;

class Solution {
    //Function to check whether the list is palindrome.
    boolean isPalindrome(Node head) {
        ArrayList 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. 反转链表一半

这种方法只反转链表的前半部分，然后将反转后的前半部分与后半部分进行比较。这种方法不需要额外的空间，空间复杂度为 O(1)。

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

        // 反转后半部分链表
        Node reversedHalf = reverseList(slow);
        Node cur = head;

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

        return true;
    }

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

优点： 空间复杂度为 O(1)，不需要额外的空间。

缺点： 代码相对复杂，需要仔细处理链表的边界条件。

注意事项

在反转链表时，一定要注意处理链表的边界条件，例如空链表、只有一个节点的链表等。
选择合适的解决方案取决于具体的应用场景。如果空间复杂度不是问题，那么创建新的反转链表或使用数组存储链表值是更简单的选择。如果空间复杂度是限制因素，那么反转链表一半是更好的选择。
理解链表操作的本质，避免直接修改原链表导致的问题。