以下是实现单链表反转的 5 种方法的示例代码：
- 递归反转
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode p = reverseList(head.next);
head.next.next = head;
head.next = null;
return p;
}- 迭代反转
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}- 交换节点反转
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next; // Temporarily store the next node
curr.next = prev; // Reverse the link
prev = curr; // Move forward on the list
curr = nextTemp; // Move forward on the list
}
return prev;
}- 使用栈
public ListNode reverseList(ListNode head) {
Deque<ListNode> stack = new LinkedList<>();
ListNode current = head;
while (current != null) {
stack.push(current);
current = current.next;
}
current = stack.poll();
ListNode newHead = current;
while (!stack.isEmpty()) {
current.next = stack.poll();
current = current.next;
}
current.next = null;
return newHead;
}- 使用头插法
public ListNode reverseList(ListNode head) {
ListNode newHead = null;
while (head != null) {
ListNode next = head.next; // Temporarily store the next node
head.next = newHead; // Reverse the link
newHead = head; // Move forward on the list
head = next; // Move forward on the list
}
return newHead;
}以上每种方法都是单链表反转的有效方式，选择合适的方法取决于特定的应用场景和性能要求。