链表反转示例代码

下面是 Java 实现链表反转的示例代码，包含迭代和递归两种方式：

public class LinkedListReverse {// 定义链表节点结构static class ListNode {int val;ListNode next;ListNode(int x) { val = x; }}// 方法1：迭代反转链表public static ListNode reverseListIterative(ListNode head) {ListNode prev = null;ListNode curr = head;while (curr != null) {ListNode nextTemp = curr.next; // 保存下一个节点curr.next = prev;              // 当前节点指向前驱prev = curr;                   // 前驱后移curr = nextTemp;               // 当前节点后移}return prev; // 返回新头节点}// 方法2：递归反转链表public static ListNode reverseListRecursive(ListNode head) {if (head == null || head.next == null) {return head;}ListNode newHead = reverseListRecursive(head.next);head.next.next = head;  // 反转指针head.next = null;       // 断开原连接return newHead;         // 返回新头节点}// 辅助方法：打印链表public static void printList(ListNode head) {ListNode curr = head;while (curr != null) {System.out.print(curr.val + " -> ");curr = curr.next;}System.out.println("null");}public static void main(String[] args) {// 创建链表 1->2->3->4->5ListNode 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.println("原始链表:");printList(head);// 迭代反转ListNode reversedIterative = reverseListIterative(head);System.out.println("迭代反转后:");printList(reversedIterative);// 递归反转（需要先重建原链表）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);ListNode reversedRecursive = reverseListRecursive(head);System.out.println("递归反转后:");printList(reversedRecursive);}
}    

代码解释：

1. 迭代方法（reverseListIterative）：

   • 使用三个指针 prev、curr 和 nextTemp 遍历链表。
   • 每次迭代将当前节点的 next 指向前驱节点，逐步反转整个链表。
   • 时间复杂度：O(n)，空间复杂度：O(1)。

2. 递归方法（reverseListRecursive）：

   • 先递归反转后续节点，再处理当前节点。
   • 将当前节点的下一节点的 next 指向当前节点，实现反转。
   • 时间复杂度：O(n)，空间复杂度：O(n)（递归栈空间）。

3. 测试示例：

   • 创建链表 1->2->3->4->5，分别用两种方法反转并打印结果。

两种方法都能有效反转链表，迭代法适合大规模数据，递归法更简洁但可能导致栈溢出。