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

链表反转后如果直接使用原始节点进行遍历可能只打印一个节点。这是因为反转后原始节点变成了尾节点 next 指针指向 null导致循环只执行一次。以下将详细介绍问题的原因和几种解决方案。问题分析在提供的代码中reverseList 函数将原地反转链表。这意味着反转后原链表的头节点 head 它实际上指向了反转后链表的尾节点。因为尾节点 next 指针为 null因此在 isPalindrome 函数中使用 head 循环只执行一次只打印第一个节点的值。解决方案从空间复杂性和实现复杂性来看提供了三种解决方案。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) 存储新链表的空间。需要修改 reverseList 函数使其创建新的节点而不是修改原链表节点 next 指针。2. 使用数组辅助判断该方法将链表中的所有节点值存储在一个数组中然后判断该数组是否为回文数组。import java.util.ArrayList; class Solution { //Function to check whether the list is palindrome. boolean isPalindrome(Node head) { ArrayListInteger 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; // Find the middle of the list while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; } // Reverse the second half of the list 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; } }注意事项该方法的空间复杂度为 O(1)但实现相对复杂。链表的中间节点需要找到链表的后半部分需要逆转。若链表长度为奇数则应注意中间节点的处理。总结本文分析了链表反转后只打印一个节点的问题并提供了三种解决方案。选择哪种方案取决于具体的应用场景和对空间复杂性的要求。如果空间复杂性不是问题可以创建新的反转链表或使用数组辅助判断。如果对空间复杂性有严格的要求则需要使用反转链表的一半。 了解链表反转的原理和各种解决方案的优缺点可以帮助开发者更有效地解决相关问题。