链表反转后，如果发现只能输出一个节点，这通常是由于在反转过程中，原链表的结构被修改，导致遍历时提前终止。具体来说，反转后的链表的原头节点变成了尾节点，而尾节点的 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; // 返回新链表的头节点
}
}注意事项:
- 务必创建新的节点，而不是直接修改原节点的指针。
2. 使用数组辅助判断
这种方法将链表中的所有元素存储到数组中，然后判断数组是否为回文。
import java.util.ArrayList;
class Solution {
//Function to check whether the list is palindrome.
boolean isPalindrome(Node head) {
ArrayList<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. 反转链表的前半部分
这种方法只反转链表的前半部分，然后将反转后的前半部分与后半部分进行比较。
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 middle node
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// Reverse the second half
Node prev = null;
Node current = slow;
Node next = null;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
Node firstHalf = head;
Node secondHalf = prev; // prev is the head of the reversed second half
// Compare the first half and the reversed second half
while (secondHalf != null) {
if (firstHalf.data != secondHalf.data) {
return false;
}
firstHalf = firstHalf.next;
secondHalf = secondHalf.next;
}
return true;
}
}注意事项:
- 需要找到链表的中间节点。
- 如果链表的长度为奇数，则中间节点不需要参与比较。
总结
链表反转是一个常见的操作，但需要注意反转过程中对原链表结构的影响。根据具体的需求，可以选择不同的解决方案，例如创建新的反转链表、使用数组辅助判断、或者仅反转链表的前半部分。在选择方案时，需要权衡空间复杂度和时间复杂度。选择哪种方法取决于具体应用场景和性能要求。
