单链表反转(Java实现)
知识储备:
源代码:
//用来反转整个链表
public void reverse(){
//判断当前链表是否为空链表,如果是空链表则结束运行,如果不是则调用重载reverse完成反转
if(isEmpty()){
return;
}
reverse(head.next);
}
//用来反转指定节点,并把反转后的节点返回
public Node reverse(Node curr){
//如果是最后一个节点,则让头节点指向最后一个节点并返回该节点
if(curr.next==null){
head.next=curr;
return curr;
}
//递归的反转当前节点curr的下一个节点,返回值就是链表反转后,当前节点的上一个节点;
Node pre=reverse(curr.next);
//让返回的节点的下一个节点变为当前节点curr;
pre.next=curr;
//把当前节点的下一个节点变为null
curr.next=null;
return curr ;
/*
* 这里的易混点:
* Node pre=reverse(curr.next); 传入的虽然是curr的下一个元素,但是当时的curr还是curr本身
* 返回的pre就是curr的下一个元素
* 然后使curr的下一个元素pre指向curr
* 然后把curr的指向置为空
* 在返回curr
* 最后一次调用时,满足了curr.next==null这个条件,就直接返回最后一个元素,而这个返回值是赋值给了倒数第二次调用的pre;
* 也就是说最后一次递归调用只是执行了if里面的步骤而已,而没有执行if外的步骤
*/
}
版权声明:本文为regens原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。