在Java中实现链表反转的方法通常可通过迭代或递归的方式来完成。以下是一种迭代方法,它使用三个指针来逐步反转链表的链接方向,这种方法对于单链表来说尤为适用,因为单链表的结点只包含数据部分和指向下一结点的指针。
下面的Java代码示例定义了链表的结构以及反转链表的函数:
首先是定义链表节点类 ListNode
:
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
this.next = null;
}
}
其次,实现反转链表函数 reverseList
:
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null; // 初始化前置节点为null
ListNode curr = head; // 当前节点为头节点
ListNode next = null; // 下一个节点初始化为null
while (curr != null) {
next = curr.next; // 保存下一个节点
curr.next = prev; // 当前节点指向前置节点,完成反转
prev = curr; // 前置节点后移
curr = next; // 当前节点后移
}
return prev; // 当循环结束时,prev指向新的头节点
}
}
该方法的工作原理如下:
- 设置三个指针
prev
、curr
和next
,分别用来跟踪前一个节点、当前节点和下一个节点。 - 遍历链表,对于每个节点,首先临时保存
next
(即curr.next
)。 - 然后更新
curr.next
指向prev
,实现反转。 prev
和curr
指针同时向前移动一个位置。- 继续这个过程,直到
curr
变为null
,这时prev
将指向原链表的最后一个节点,也就是反转后的头节点。
反转链表是链表操作中的基础技术之一,它不仅可以作为单独的功能来使用,还经常被当做其他复杂链表问题的一个步骤。熟练掌握链表反转对于理解链表相关的算法题至关重要。
这种反转方法不需要使用额外的存储空间,因此空间复杂度为,它只需要遍历一次链表,所以时间复杂度为,其中为链表的长度。这使得这种反转链表的方法既高效又实用。