单向链表反转java实现头插法（java实现反转单向链表的方法）

编程日记 • 2025-08-02 22:17 • 阅读 59

前言：

题目：

方法一：迭代法

方法二：头插法

方法三：递归法

方法四：栈辅助

总结：

本文阅读基础：有一定的数据结构知识，了解单向链表。

单向链表：1,2,3,4,5 反向输出，期待：5,4,3,2,1

定义一个单向链表：

main方法：

思路：从第二个开始，逐个反转

关键：将当前节点的下一个节点记下；将当前节点和已有的head反转，使当前节点做为新的head；

第一次进入：head =1,cur = 2(2->3->4->5);

第二次进入：head =2(2->1),cur = 3(3->4->5);

第三次进入：head =3(3->2->1),cur = 4(4->5);

第四次进入：head =4(4->3->2->1),cur = 5(5->null);

思路：使用一个空节点作为反转后链表的头,每次将原链表的头节点插入到空节点后面,最后返回新链表的头节点。

关键：返回newHead 的next

第一次进入：newHead = 0,head = 1(1->2->3->4->5);

第二次进入：newHead = 0(0->1),head = 2(2->3->4->5);

第三次进入：newHead = 0(0->2->1),head = 3(3->4->5);

第四次进入：newHead = 0(0->3->2->1),head = 4(4->5);

第五次进入：newHead = 0(0->4->3->2->1),head = 5(5->null);

（也可以在开始将newHead.next()设置为1，能减少一次循环）

递归法比较有意思，大家可以结合之前我们聊过的内存分析来理解递归法[Java基础]面向对象-内存解析_小王师傅66的博客-CSDN博客

关键：递归的入口是head.next，不是head，才能递归到最后两个节点

当head = 4时，head.next()=5,执行到reverseList()方法时返回head。

此时：5<-4<-3<-2<-1，newHead = 5, head= 4(4->5)，经过2,3反转得到：5->4 , 3<-2<-1；

(在第3步，我们已经将4.next置为null);

所以过程如下：

1）5 , 4<-3<-2<-1；

2）5->4 , 3<-2<-1；

3）5->4->3, 2<-1；

4) 5->4->3->2, 1;

最后输出newHead = 5(5->4->3->2->1).

这个方法就比较简单了，用的Java的工具包Stack类。我们知道栈的特点是先进后出，所以思路就是：将所有节点依次入栈,然后出栈的顺序就是反转后的顺序,根据这个顺序重建链表。

方法比较简单，这里我就不列举值的变化了，大家可以自行推导一下。

主要区别在于迭代法和递归法是在原链表上直接反转,无需额外空间;而头插法和栈辅助需要 O(N) 的额外空间。一般迭代法代码最简洁,递归法需要处理终止条件,但思路清晰。

当然还有很多反转链表的方法，以上只是列举4种典型的方法。通过这4种方法，我们可以看到，思路不一样，实现方法完全不一样。