java代码如何实现链表的反转操作 java代码链表操作的基础实现方法-java教程-PHP中文网

链表反转的核心是调整每个节点的next指针方向，1. 迭代法使用三个指针prev、curr和nexttemp，通过循环将每个节点的next指向前一个节点，最终prev指向新头节点，时间复杂度o(n)，空间复杂度o(1)；2. 递归法基于“先反转后续链表再调整当前节点”的思想，基本情况是空节点或单节点，递归反转head.next后，将head.next.next指向head并置head.next为null，返回原链表尾节点作为新头，时间复杂度o(n)，空间复杂度o(n)；实际开发中需注意空链表和单节点的边界处理、指针顺序维护以防链表断裂，首选迭代法以避免递归导致的栈溢出风险，两种方法均需确保正确引用节点以利于gc回收，此操作完整实现了链表基础定义与核心操作的综合应用。

java代码如何实现链表的反转操作 java代码链表操作的基础实现方法

链表反转，在Java代码里实现，核心其实就是调整每个节点的

next

登录后复制

指针方向。这不像数组反转那么直接，你不能简单地交换元素位置，因为链表是靠指针串联起来的。所以，我们得小心翼翼地把每个节点指向它原本的前一个节点，而不是后一个。至于链表的基础操作，无非就是节点的定义、插入、删除和遍历，这些都是为了能玩转链表而必须掌握的。

解决方案

要实现链表的反转，最常用也最稳妥的方法就是迭代法。这个方法不需要额外的存储空间（除了几个指针变量），而且效率很高。

想象一下，你有一串珠子，它们被一根线串起来。现在你想让这串珠子反过来，你就得把线从每个珠子后面抽出来，再从前面穿进去。在代码里，这根“线”就是

next

登录后复制

指针。

立即学习“Java免费学习笔记（深入）”；

我们需要三个指针来完成这个“穿线”的过程：

```
prev
```
登录后复制
(previous): 指向当前节点的前一个节点。一开始，它什么都没有，所以是
```
null
```
登录后复制
。
```
curr
```
登录后复制
(current): 指向我们正在处理的当前节点。一开始，它就是链表的头节点。
```
nextTemp
```
登录后复制
(next temporary): 这是一个临时指针，用来保存
```
curr
```
登录后复制
节点的下一个节点。为什么需要它？因为我们马上就要改变
```
curr.next
```
登录后复制
的指向了，如果不提前存起来，我们就找不到下一个要处理的节点了。

循环会一直进行，直到

curr

登录后复制

变成

null

登录后复制

，这意味着我们已经遍历了整个链表。在每一次循环中：

我们先用
```
nextTemp
```
登录后复制
把
```
curr
```
登录后复制
的下一个节点“记住”。
然后，把
```
curr
```
登录后复制
的
```
next
```
登录后复制
指针指向
```
prev
```
登录后复制
。这是反转的核心一步。
接着，
```
prev
```
登录后复制
向前移动，变成当前的
```
curr
```
登录后复制
。
最后，
```
curr
```
登录后复制
也向前移动，变成之前用
```
nextTemp
```
登录后复制
记住的那个节点。

这样一步步走下来，当循环结束时，

prev

登录后复制

指针就会指向原链表的最后一个节点，也就是反转后链表的头节点。

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

public class LinkedListReversal {

    /**
     * 迭代法反转链表
     *
     * @param head 链表的头节点
     * @return 反转后链表的头节点
     */
    public ListNode reverseListIterative(ListNode head) {
        ListNode prev = null; // 指向前一个节点，初始为null
        ListNode curr = head; // 指向当前节点，初始为链表头

        while (curr != null) {
            ListNode nextTemp = curr.next; // 临时保存当前节点的下一个节点
            curr.next = prev;              // 将当前节点的next指针指向前一个节点，实现反转

            prev = curr;                   // prev指针向前移动，指向当前节点
            curr = nextTemp;               // curr指针向前移动，指向下一个待处理的节点
        }
        return prev; // 循环结束后，prev就是新链表的头节点
    }

    // 辅助方法：打印链表
    public void printList(ListNode head) {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        LinkedListReversal reverser = new LinkedListReversal();

        // 构建一个链表: 1 -> 2 -> 3 -> 4 -> 5
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        System.out.print("原始链表: ");
        reverser.printList(head);

        // 反转链表
        ListNode reversedHead = reverser.reverseListIterative(head);

        System.out.print("反转后链表: ");
        reverser.printList(reversedHead);

        // 测试空链表和单节点链表
        System.out.println("\n--- 测试特殊情况 ---");
        System.out.print("空链表反转: ");
        reverser.printList(reverser.reverseListIterative(null));

        System.out.print("单节点链表反转: ");
        reverser.printList(reverser.reverseListIterative(new ListNode(100)));
    }
}

登录后复制

链表在Java中如何定义和实现基础操作？

在Java里，链表本身并不是一个内置的数据结构，我们通常是通过自定义的

Node

登录后复制

（或

ListNode

登录后复制

）类来构建它。一个最简单的链表节点，至少需要两个东西：一个用来存数据的值（比如

int val

登录后复制

），另一个就是指向下一个节点的引用（

ListNode next

登录后复制

）。

// 这是最基本的节点定义，上面已经有了，这里再强调一下
class ListNode {
    int val;       // 节点存储的数据
    ListNode next; // 指向下一个节点的引用

    ListNode(int x) {
        val = x;
        next = null; // 构造新节点时，默认下一个是空的
    }
}

登录后复制

有了节点，我们就可以实现一些基础操作了。这些操作是理解和操作链表的基础，说实话，很多时候链表的题目就是围绕这些基本操作的变种。

插入节点 (在尾部)：如果你想在链表末尾加一个新节点，你需要从头开始遍历，直到找到最后一个节点（就是

next

登录后复制

为

null

登录后复制

的那个），然后把新节点挂在它后面。

public void addNodeAtEnd(ListNode head, int val) {
    ListNode newNode = new ListNode(val);
    if (head == null) { // 如果链表是空的，新节点就是头
        // 实际上，这里需要一个外部变量来更新head，
        // 否则在方法内部更新head不会影响外部引用
        // 通常我们会有一个LinkedList类来管理head
        // 简单起见，这里假设head是传入的第一个节点
        return; // 实际应用中，会返回newNode作为新的head
    }
    ListNode current = head;
    while (current.next != null) {
        current = current.next;
    }
    current.next = newNode;
}

登录后复制

插入节点 (在头部)：这个就简单多了。创建一个新节点，让它的
```
next
```
登录后复制
指向当前的头节点，然后把这个新节点设为新的头节点。
```
public ListNode addNodeAtBeginning(ListNode head, int val) {
    ListNode newNode = new ListNode(val);
    newNode.next = head;
    return newNode; // 新的头节点
}
```
登录后复制

删除节点 (按值)：要删除一个特定值的节点，你得遍历链表。如果找到匹配的节点，你需要把它的前一个节点的

next

登录后复制

指针直接指向被删除节点的下一个节点，这样就“跳过”了那个要删除的节点。如果删除的是头节点，那就直接把头节点指向它的下一个。

public ListNode deleteNodeByValue(ListNode head, int val) {
    if (head == null) {
        return null;
    }
    if (head.val == val) { // 如果头节点就是要删除的
        return head.next;
    }
    ListNode current = head;
    while (current.next != null && current.next.val != val) {
        current = current.next;
    }
    if (current.next != null) { // 找到了要删除的节点
        current.next = current.next.next;
    }
    return head;
}

登录后复制

遍历链表 (打印)：这个是最基础的，从头节点开始，沿着
```
next
```
登录后复制
指针一个接一个地访问，直到遇到
```
null
```
登录后复制
。
```
// 已经包含在上面的示例代码中
public void printList(ListNode head) {
    ListNode current = head;
    while (current != null) {
        System.out.print(current.val + " -> ");
        current = current.next;
    }
    System.out.println("null");
}
```
登录后复制
这些操作，说白了，就是围绕着
```
head
```
登录后复制
和各个节点的
```
next
```
登录后复制
指针做文章。理解了这些，链表的问题就没那么神秘了。

Devv
Devv是一个专为程序员打造的新一代AI搜索引擎

140

查看详情

链表反转操作的两种常见实现思路是什么？

除了上面详细讲的迭代法，链表反转还有另一种非常经典的实现思路——递归法。这两种方法各有特点，理解它们能让你对链表操作的理解更上一层楼。

1. 迭代法 (Iterative Approach)

这个我们上面已经详细讲过了，它的核心思想就是“三指针”大法：

prev

登录后复制

、

curr

登录后复制

、

nextTemp

登录后复制

。一步步地改变当前节点的

next

登录后复制

指向，同时移动这三个指针，直到遍历完整个链表。

优点：
- 空间复杂度是O(1)，因为它只用了常数个额外的指针变量。对于很长的链表，这非常重要，不会有栈溢出的风险。
- 性能稳定，没有递归调用栈的开销。
缺点：
- 逻辑上可能比递归稍微难理解一点点，需要脑子里清晰地模拟指针的移动过程。

2. 递归法 (Recursive Approach)

递归法反转链表，初看起来可能有点绕，但一旦理解了它的精髓，你会觉得它非常巧妙。它的基本思想是：

基本情况 (Base Case)：如果链表是空的（
```
head == null
```
登录后复制
）或者只有一个节点（
```
head.next == null
```
登录后复制
），那它本身就是反转的，直接返回
```
head
```
登录后复制
。这是递归的终止条件。
递归步骤 (Recursive Step)：对于一个非空且不止一个节点的链表，我们假设除了头节点之外的“剩余部分”（
```
head.next
```
登录后复制
）已经通过递归调用被反转了。那么，现在我们只需要把当前头节点
```
head
```
登录后复制
接到反转后的“剩余部分”的尾巴上。

具体来说：

```
newHead = reverseListRecursive(head.next);
```
登录后复制
这行代码会一直递归下去，直到链表的最后一个节点，并把这个最后一个节点作为
```
newHead
```
登录后复制
返回。
当递归开始向上返回时，比如当前处理的是节点A，它的下一个是节点B。递归调用已经把B以及B后面的所有节点都反转了。现在
```
head
```
登录后复制
是A，
```
head.next
```
登录后复制
是B。反转后的B及其后面的链表，其头部是原来的尾部。
我们要做的是让B的
```
next
```
登录后复制
指向A，即
```
head.next.next = head;
```
登录后复制
。
然后，A的
```
next
```
登录后复制
应该指向
```
null
```
登录后复制
，因为A现在是它所在局部反转链表的尾部，即
```
head.next = null;
```
登录后复制
。
最后，返回最开始递归调用时得到的那个
```
newHead
```
登录后复制
，它就是整个链表反转后的新头。

public ListNode reverseListRecursive(ListNode head) {
    // 基本情况：链表为空或只有一个节点，直接返回
    if (head == null || head.next == null) {
        return head;
    }

    // 递归反转head.next开始的子链表
    // newHead会是原链表的最后一个节点，也是反转后链表的头节点
    ListNode newHead = reverseListRecursive(head.next);

    // 完成当前节点的反转：
    // head.next (即原链表的下一个节点) 的 next 指向 head
    // 比如 1 -> 2 -> 3，当处理到1时，newHead是3。
    // 此时 head=1, head.next=2。
    // 递归返回时，2 -> 3 已经反转成 3 -> 2。
    // 现在 2 的 next 指向 1 (head.next.next = head;)
    // 1 的 next 指向 null (head.next = null;)
    head.next.next = head;
    head.next = null;

    return newHead; // 每次都返回最开始的那个新头节点
}

登录后复制

优点：
- 代码看起来更简洁、优雅，符合函数式编程的思维。
缺点：
- 空间复杂度是O(N)，因为每次递归调用都会占用栈空间，链表越长，栈深度越大。对于非常长的链表，可能会导致栈溢出（StackOverflowError）。
- 性能上通常不如迭代法，有额外的函数调用开销。

在实际开发中，如果对链表长度没有严格限制，或者担心栈溢出，迭代法通常是更稳妥的选择。但如果你觉得递归的逻辑更清晰，且链表长度可控，递归法也未尝不可。

在实际开发中，链表反转的常见陷阱和性能考量有哪些？

在实际操作链表反转时，有一些细节和潜在问题是需要注意的，特别是对于那些初学者来说，一不小心就可能掉进坑里。

1. 空链表和单节点链表 这是最常见的边缘情况。如果传入的

head

登录后复制

是

null

登录后复制

（空链表），或者

head.next

登录后复制

也是

null

登录后复制

（单节点链表），你的反转逻辑必须能够正确处理。

陷阱：很多新手在写循环或递归时，没有考虑
```
head == null
```
登录后复制
或
```
head.next == null
```
登录后复制
的情况，导致空指针异常。
处理：迭代法中，
```
while (curr != null)
```
登录后复制
自然会处理空链表，因为
```
curr
```
登录后复制
一开始就是
```
null
```
登录后复制
，循环不执行，直接返回
```
prev
```
登录后复制
（也就是
```
null
```
登录后复制
）。单节点链表也是一样，循环一次就结束，
```
prev
```
登录后复制
会是那个唯一的节点。递归法中，
```
if (head == null || head.next == null)
```
登录后复制
就是专门处理这些基本情况的。

2. 指针的正确维护 这是链表操作的核心，也是最容易出错的地方。

陷阱：在迭代法中，如果你没有先用
```
nextTemp
```
登录后复制
保存
```
curr.next
```
登录后复制
，然后直接修改了
```
curr.next
```
登录后复制
的指向，那么你就失去了对链表后续部分的引用，链表就“断”了。
处理：务必牢记“三指针”的顺序和作用：先保存下一个，再反转当前，最后移动指针。

3. 内存管理 (Java中的GC) 虽然Java有垃圾回收机制（GC），不像C/C++那样需要手动

free

登录后复制

内存，但理解其原理有助于避免潜在的内存泄漏（虽然在链表反转中不常见）。

陷阱：如果你在反转过程中不小心丢失了对某些节点的引用，它们就可能变成“孤儿”节点，虽然会被GC回收，但如果逻辑错误导致大量节点无法被正确引用，可能会造成短暂的内存压力。
处理：确保所有节点在反转前后都能被正确引用，或者被GC识别为可回收。在链表反转中，只要你正确地调整了
```
next
```
登录后复制
指针，所有节点最终都会被新链表引用，或者被GC回收。

4. 性能考量

时间复杂度：无论是迭代法还是递归法，它们都需要遍历链表中的每一个节点一次。所以，它们的时间复杂度都是O(N)，其中N是链表的长度。这是最优的，因为你至少要访问每个节点一次才能完成反转。
空间复杂度：
- 迭代法：O(1)。它只需要常数个额外的指针变量来完成操作，不依赖于链表长度。这是它最大的优势。
- 递归法：O(N)。每次递归调用都会在函数调用栈中创建一个新的栈帧，链表有多长，递归深度就有多深。对于非常长的链表（比如几十万个节点），这可能导致栈溢出错误（StackOverflowError）。
选择依据：
- 首选迭代法：在绝大多数实际开发场景中，迭代法是更推荐的选择，因为它没有栈溢出的风险，且空间效率更高。
- 递归法的适用场景：如果你确信链表长度不会太长（比如几千个节点以内），或者你更看重代码的简洁性和递归思维的训练，那么递归法也是可以接受的。但在面试或生产环境中，通常会倾向于迭代法。