Java怎么实现反转链表

# Java怎么实现反转链表

反转链表是数据结构与算法中的经典问题，也是面试高频考点。本文将介绍Java中两种常见的反转链表实现方法：**迭代法**和**递归法**，并提供完整代码示例。

## 一、链表节点定义
首先定义链表节点类：
```java
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

二、迭代法实现

时间复杂度O(n)，空间复杂度O(1)

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode nextTemp = curr.next; // 临时保存下一个节点
        curr.next = prev;  // 反转指针方向
        prev = curr;       // prev指针后移
        curr = nextTemp;   // curr指针后移
    }
    return prev;  // 新链表头节点
}

三、递归法实现

时间复杂度O(n)，空间复杂度O(n)（栈空间）

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode newHead = reverseList(head.next);
    head.next.next = head;  // 反转指针方向
    head.next = null;       // 断开原指针
    return newHead;
}

四、方法对比

五、测试示例

// 输入: 1->2->3->4->5->NULL
// 输出: 5->4->3->2->1->NULL
ListNode head = new ListNode(1);
head.next = new ListNode(2);
// ...构建链表
ListNode reversed = reverseList(head);

掌握这两种实现方式可以帮助开发者深入理解链表结构和指针操作，建议同时掌握两种写法以应对不同场景需求。 “`