怎么理解Java递归单链表反转

发布时间:2021-11-04 16:56:16 作者:iii
来源:亿速云 阅读:257

这篇文章主要讲解了“怎么理解Java递归单链表反转”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“怎么理解Java递归单链表反转”吧!

首先,咱们要先明确,什么是递归。递归就是自己调用自己对吧。比如:有一个函数为 f(n) = f(n-1) * n  ,(注意,我这里是举例子,这个函数没有给出递归的结束条件)给 n 赋值为 5 , 则:

--> f(5) --> 5 * f(4) --> 5 * ( 4 * f(3)) --> 5 * ( 4 * (3 * f(2))) --> 5 * ( 4 * ( 3 * ( 2 * f (1)))) --> 5 * ( 4 * ( 3 * ( 2 * 1))) --> 5 * ( 4 * ( 3 * 2)) --> 5 * ( 4 * 6 ) --> 5 * 24 --> 120

在看完例子之后,咱们接下来不 BB ,直接 show code:

/**  * 单链表反转---递归实现  */ public class ReverseSingleList {     public static class Node{         private int data;         private Node next;          public Node( int data , Node next){             this.data = data;             this.next = next;         }          public int getData(){return  data;}     }     public static void main(String[] args){         // 初始化单链表         Node node5 = new Node(5,null);         Node node4 = new Node(4,node5);         Node node3 = new Node(3,node4);         Node node2 = new Node(2,node3);         Node node1 = new Node(1,node2);          // 调用反转方法         Node recursiveList = recursiveList(node1);         System.out.println(recursiveList);     }     /**      *递归实现单链表反转      * @param list 为传入的单链表      */     public static Node recursiveList(Node list){         // 如果链表为空 或者 链表中只有一个节点,直接返回         // 也是递归结束的条件         if (list == null || list.next == null) return list;         Node recursive = recursiveList(list.next);         // 将 list.next.next 指针指向当前链表 list         list.next.next = list ;         // 将 list.next 指针指向 null         list.next = null;         // 返回反转之后的链表 recursive         return recursive;     } }

经过上面的代码,应该能够看到核心代码就是,递归实现单链表反转部分的那 5 行代码,别小看了这 5 行代码,想要真正弄清楚还真的挺不容易的。

我把这 5 行代码贴在这里,咱们一行行分析,争取看完这篇博客就能懂~(注释我就去掉了,咱们专心看这几行核心代码)

if (list == null || list.next == null) return list; Node recursive = recursiveList(list.next); list.next.next = list ; list.next = null; return recursive;

第一行就是一个判断,条件不满足,那就往下走,第二行是自己调用自己,程序又回到第一行,不满足条件程序向下执行,自己调用自己

就这样循环到符合条件为止,那么什么时候符合条件呢?也就是 list == null 或者 list.next == null 时,看一下自己定义的链表是  1->2->3->4->5->null ,所以符合条件时,此时的链表为 5->null  ,符合条件之后,程序继续向下执行,在执行完 Node recursive = recursiveList(list.next);  这行代码之后,咱们来看一下此时的程序执行结果:

怎么理解Java递归单链表反转

我把上面这个给画出来(阿粉的画工不是不好,不要在乎它的美丑~)

怎么理解Java递归单链表反转

接下来程序该执行 list.next.next = list 执行结束之后,链表大概就是这个样子:

怎么理解Java递归单链表反转

那是图,下面是程序断点调试程序的结果,发现和上面的图是一样的:

怎么理解Java递归单链表反转

程序继续向下走 list.next = null ,也就是说,将 list 的 next 指针指向 null :

怎么理解Java递归单链表反转

从图中看到, list 为 4->null , recursive 为 5->4->null  ,咱们来看看程序的结果,是不是和图相符:

怎么理解Java递归单链表反转

完全一样有没有!

OK ,还记得咱们刚开始的递归函数例子嘛?现在执行完毕,开始执行下一次,咱们继续来看,此时的链表是这个样子的:

怎么理解Java递归单链表反转

接下来程序执行的代码就是四行了:

Node recursive = recursiveList(list.next); list.next.next = list ; list.next = null; return recursive;

继续执行程序,咱们来看结果,将 list.next.next = list 运行结束时,此时链表为:

怎么理解Java递归单链表反转

从图中能够看到,链表 list 为 3->4->3->4 循环中, recursive 为  5->4->3->4->3 循环,咱们看一下程序是不是也是如此(在这里我截了两个循环作为示例):

怎么理解Java递归单链表反转

接下来程序执行 list.next = null ,执行完毕之后,就是将 list 的 next 指针指向 null :

怎么理解Java递归单链表反转

从图中能够看出来, list 为 3->null , recursive 为 5->4->3->null  ,上图看看实际结果和分析的是否一致:

怎么理解Java递归单链表反转

说明什么?!说明咱们上面的分析是正确的。接下来的程序分析,读者们就自行研究吧,相信接下来的分析就难不倒咱们聪明的读者啦~

反转单链表的前 N 个节点

OK ,咱们趁热打铁一下,刚刚是通过递归实现了整个单链表反转,那如果我只是想反转前 N 个节点呢?

比如单链表为 1->2->3->4->5->null ,现在我只想反转前三个节点,变为  3->2->1->4->5->null

有没有想法?

咱们进行整个单链表反转时,可以理解为传递了一个参数 n ,这个 n  就是单链表的长度,然后递归程序不断调用自己,然后实现了整个单链表反转。那么,如果我想要反转前 N 个节点,是不是传递一个参数 n 来解决就好了?

咱们就直接上代码了:

/**    *反转单链表前 n 个节点    * @param list 为传入的单链表 , n 为要反转的前 n 个节点    */   public static Node next;   public static Node reverseListN(Node list,int n){       if (n == 1) {           // 要进行反转链表时,先将 list 后的节点数据保存到 next 中           next = list.next;           return  list;       }        Node reverse = reverseListN(list.next , n-1);       list.next.next = list;       // 将 list.next 的指针指向没有进行反转的链表       list.next = next ;       return reverse;   }

反转单链表的一部分

既然反转整个单链表实现了,反转前 N 个节点实现了,那么如果有个需求是反转其中的一部分数据呢?大概就是这样,原来的链表为  1->2->3->4->5->null ,反转其中的一部分,使反转后的链表为  1->4->3->2->5->null

借用反转前 N 个节点的思路,是不是我传两个参数进来,一个是开始反转的节点,一个是结束反转的节点,然后递归操作就可以了?

瞅瞅代码是怎么写的:

/**  *反转部分单链表  * @param list 为传入的单链表, m 为开始反转的节点, n 为结束的反转节点  */ public static Node reverseBetween(Node list , int m , int n){     if (m == 1){         return reverseListN(list,n);     }     list.next = reverseBetween(list.next,m-1,n-1);     return list; }

感谢各位的阅读,以上就是“怎么理解Java递归单链表反转”的内容了,经过本文的学习后,相信大家对怎么理解Java递归单链表反转这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是亿速云,小编将为大家推送更多相关知识点的文章,欢迎关注!

推荐阅读:
  1. java递归和非递归的实现
  2. Java递归获得TreeJson

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

java

上一篇:如何制作一个成功的地方网站

下一篇:windows server管理员工具包rktools.exe的示例分析

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》