在链表操作中反转链表是一项常见的任务。然而在实现过程中开发人员可能会遇到一些意想不到的问题比如反转链表只打印一个节点。这通常是由于对链表结构的不完全理解造成的。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) { ListInteger 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; }这种方法只逆转链表的一半只需要常数级别的额外空间。总结在反转链表时除非这是你的初衷否则不要直接修改原链表的结构。如果您需要保留原始链表请创建新的链表进行反转。此外还可以考虑使用数组辅助判断或只反转链表的一半来解决问题。选择哪种方法取决于具体需求和空间复杂性。了解链表的结构和操作模式是解决此类问题的关键。
解决反转链表后只打印一个节点的问题
在链表操作中反转链表是一项常见的任务。然而在实现过程中开发人员可能会遇到一些意想不到的问题比如反转链表只打印一个节点。这通常是由于对链表结构的不完全理解造成的。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) { ListInteger 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; }这种方法只逆转链表的一半只需要常数级别的额外空间。总结在反转链表时除非这是你的初衷否则不要直接修改原链表的结构。如果您需要保留原始链表请创建新的链表进行反转。此外还可以考虑使用数组辅助判断或只反转链表的一半来解决问题。选择哪种方法取决于具体需求和空间复杂性。了解链表的结构和操作模式是解决此类问题的关键。
