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

在链表操作中，反转链表是一项常见的任务。然而，在实现过程中，开发人员可能会遇到一些意想不到的问题，比如反转链表只打印一个节点。这通常是由于对链表结构的不完全理解造成的。

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. 使用数组辅助判断

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

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

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

总结

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