单链表的翻转java

### Java 实现单链表反转的方法 #### 方法一：迭代法 通过迭代的方式逐个节点进行反转操作。此方法利用三个指针变量 `pre`、`current` 和 `next` 来完成链表的反转。 ```java public class LinkedList { public static ListNode reverseList(ListNode node) { ListNode pre = null; ListNode current = node; while (current != null) { ListNode next = current.next; // 记录下一个节点 current.next = pre; // 当前节点指向前一个节点 pre = current; // 前移一位 current = next; // 移动到下个节点继续处理 } return pre; // 返回新的头结点 } /// 定义链表结构体 public static class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } } ``` 这种方法的时间复杂度为 O(n)，空间复杂度为 O(1)[^5]。 #### 方法二：递归法 采用递归方式来实现链表反转，该方法的核心在于不断调用自身直到遇到最后一个非空节点作为新的头部，再逐步回溯建立反向连接关系。 ```java public class Solution { 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; } /// 链表定义同上... } ``` 这段代码展示了如何使用递归来达到相同的效果[^2]。 #### 方法三：辅助数据结构（数组） 可以将原链表中的元素存储在一个临时列表或者数组里，之后按照相反顺序重新构建一个新的链表。 ```java import java.util.ArrayList; import java.util.Collections; public class ReverseLinkedListWithArray { public static ListNode reverseUsingArrayList(ListNode head, int count){ ArrayList<Integer> listValues = new ArrayList<>(); ListNode temp = head; // 将链表值存入list中 while(temp != null){ listValues.add(temp.val); temp = temp.next; } Collections.reverse(listValues); // 创建新链表并填充已逆序的数据 ListNode reversedHead = null; ListNode tail = null; for(Integer value : listValues){ ListNode newNode = new ListNode(value); if(reversedHead==null){ reversedHead=newNode; tail=reversedHead; }else{ tail.next=newNode; tail=tail.next; } } return reversedHead; } /// 链表定义同上... } ``` 这种方式虽然简单易懂但是效率较低，并且额外占用了内存资源[^1]。 以上就是三种常见的Java实现单链表反转的技术方案，每一种都有其特点，在实际应用时可以根据具体需求选择合适的方法。