解决链表反转后只输出一个节点的问题-java教程-PHP中文网

解决链表反转后只输出一个节点的问题

霞舞

发布： 2025-09-28 15:31:01

原创

575人浏览过

解决链表反转后只输出一个节点的问题

链表反转后，如果发现只能输出一个节点，这通常是由于在反转过程中，原链表的结构被修改，导致遍历时提前终止。具体来说，反转后的链表的原头节点变成了尾节点，而尾节点的 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. 使用数组辅助判断

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

AI建筑知识问答

用人工智能ChatGPT帮你解答所有建筑问题

查看详情

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

登录后复制

注意事项: