反转链表Java

### 链表反转的实现方式 链表是一种线性数据结构，其每个节点包含一个数据元素和指向下一个节点的引用。在 Java 中，链表可以通过自定义类来实现，并且可以通过多种方法对链表进行反转操作。 #### 1. 迭代法实现链表反转 这种方法通过遍历链表并逐个调整节点的指针方向来实现反转。具体步骤如下： - 定义三个指针 `pre`、`current` 和 `next`。 - 初始化 `pre` 为 `null`，`current` 指向头节点。 - 遍历链表时，先保存当前节点的下一个节点到 `next`。 - 将 `current.next` 指向 `pre`，完成指针反转。 - 更新 `pre` 为 `current`，`current` 为 `next`。 - 当 `current` 变为空时，新的头节点为 `pre`。 ```java public class MyLinkedList { private ListNode head = new ListNode(0); // 带头结点的链表 public static class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } // 迭代法反转链表 public ListNode reverseList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode pre = null; ListNode current = head; while (current != null) { ListNode next = current.next; // 保存下一个节点 current.next = pre; // 反转指针 pre = current; // 移动pre current = next; // 移动current } return pre; // 新的头节点 } } ``` #### 2. 递归法实现链表反转 递归方法通过将问题分解为子问题来解决。它会一直递归到最后一个节点，然后逐步反转指针。 - 如果链表为空或只有一个节点，直接返回该节点。 - 递归调用函数处理下一个节点。 - 在回溯过程中，将当前节点的下一个节点的 `next` 指向当前节点。 - 最后将当前节点的 `next` 设为 `null`。 ```java public ListNode reverseList3(ListNode pHead){ if(pHead == null || pHead.next == null){ return pHead; } ListNode pNext = pHead.next; pHead.next = null; ListNode reverseHead = reverseList3(pNext); pNext.next = pHead; return reverseHead; } ``` #### 3. 头插法实现链表反转 头插法是利用一个新的链表头部，每次从原链表中取出一个节点插入到新链表的头部，从而实现反转[^3]。 - 创建一个新的头节点 `reverseHead`。 - 遍历原始链表，将每一个节点插入到 `reverseHead` 的前面。 - 最后将原始头节点的 `next` 指向 `reverseHead.next`。 ```java public static void reverseList(HeroNode head) { if(head.next == null || head.next.next == null) { return; } HeroNode cur = head.next; HeroNode next = null; HeroNode reverseHead = new HeroNode(0, "", ""); while(cur != null) { next = cur.next; cur.next = reverseHead.next; reverseHead.next = cur; cur = next; } head.next = reverseHead.next; } ``` ### 总结 以上三种方法均可以在 Java 中实现链表的反转。迭代法适用于大多数情况，代码逻辑清晰；递归法更简洁，但可能会导致栈溢出；头插法则适合需要修改原链表结构的情况。根据实际需求选择合适的方法即可[^1][^2][^3][^4][^5]。 ---