超超超超超超超详细的链表反转解析,超长解析,附加debug运行结果图
本帖最后由 肖-肖 于 2021-5-4 16:51 编辑题目在注释中,然后这个是我用java写的,真的每行代码基本都由注释不能再详细了吧
代码如下:
/**
链表反转-将单链表的链接顺序反转过来
例如:输入: 1->2->3->4->5
输出: 5->4->3->2->1
节点用Node表示 next代表箭头
*/
public class ReverseList {
//内部类 他就是一个节点类型 也就是说ListNode是链表中的一个节点
static class ListNode{
int val;//代表链表中的值
ListNode next;//代表链表中的指针
//这个内部类的构造器
public ListNode(int val,ListNode next){
this.val=val;
this.next=next;
}
}
//一个返回值为节点类型的方法 参数也是节点 传入一个head相当于传入了整条链表因为有next指针指向下一个节点
public static ListNode iterate(ListNode head){
//定义两个变量在这里 主要适用于存放上一个和下一个节点 有点像交换两个数中间也有中间变量只不过这个名字比较牛实际不是
ListNode prev=null,next;//prev为null是因为第一个节点的前一个是null
ListNode curr=head;//首先当前变量肯定是head头节点啊
//第一种方法:迭代
//由于我们不知道这个链表到底有多长 所以使用while循环 且由于传入的是一个ListNode是一个节点
//循环变量用来记录循环到什么位置了-当前元素curr 相当于for循环中的i
//且循环的终止条件是:next指针指向的下一个元素是null
while(curr != null)
{
//保存当前节点的next指针到变量next
next = curr.next;
//把prev给了前面的下一个
curr.next = prev;//也就是将当前节点的指针指向前一个的值
//此时prev还需要赋值
//先把curr赋值给prev
prev = curr;//相当于prev保存了curr 也就是保存了当前节点 也就是1节点保存到了prev中 和下一个的顺序千万不要反
curr = next;//将当前节点赋值为下一个节点的变量 也就是相当于1变成2了 也就是再把next变成当前的元素 然后跟着进入下一次循环
}
return prev;//最后返回prev节点就可以了 最后prev指向的就是末尾元素的前一个节点 也就是null前面的那个节点 当然值应该保存到是5
}
//链表反转-方法二-递归实现
public static ListNode recursion(ListNode head){
//注意点:迭代的话要从后便开始也就是从5开始
//如果你传过来的链表本身是空，以及head的next为空的话意味着已经到了最后一个元素，意味着可以递归了 那不就可以返回了嘛
if(head == null || head.next == null )
{
//那么无需反转 直接将这个head节点返回就可以了
return head;//这个例子的话 就代表是第五个节点返回5 debug过了
}
//用递归的方式找到最后一个节点 并赋值给new_head
ListNode new_head = recursion(head.next);//因为迭代的时候head会变为4 debug过了确实如此
//因为我要返回第一个节点的，本来5是最后一个元素但是我现在要把它变成第一个元素而recursion(head.next)返回的就是第一个元素6啊
//相当于吧4和5之间的指针拆开了，从而把5的next指向4 也就是会从5(head)开始然后->4->3
head.next.next = head;//所以这里就是5.next=4 也就是5指向了4 一步步debug猜出来的呀 辛苦啊
head.next = null;//避免环型链表的出现
return new_head;
}
public static void main(String[] args) {
//下边是链表的结构 初始化了5个节点
ListNode node5 = new ListNode(5,null);
ListNode node4 = new ListNode(4,node5);
ListNode node3 = new ListNode(3,node4);
ListNode node2 = new ListNode(2,node3);
ListNode node1 = new ListNode(1,node2);
//我们调用方法只需将node1节点传入即可-实际上就是head节点
//测试第一种迭代的方法 会返回prev节点
//ListNode prev = iterate(node1);//这里我门最先穿的是1哦
//测试第二种递归的方法 同样加断点
ListNode prev = recursion(node1);
//下一行打断点
System.out.println(prev);
}
}
debug后的运行结果图
话说今天有点感冒真的不在状态
页:
[1]