单链表反转 递归法Java实现
-
经历了很多面试,面试官最爱考察的算法无非是斐波那契数列和单链表反转,尽管是这些都是基础知识,然而我对单链表反转有更多的想法。 递归法是我早期最爱在面试中使用的算法,很有逼格,写起来非常优雅,非常好理解。
先定义链表数据结构
static class Node { Integer data; Node next; } static Node readyNode() { Node linkNode1 = new Node(); linkNode1.data = 1; Node linkNode2 = new Node(); linkNode2.data = 2; Node linkNode3 = new Node(); linkNode3.data = 3; Node linkNode4 = new Node(); linkNode4.data = 4; Node linkNode5 = new Node(); linkNode5.data = 5; Node linkNode6 = new Node(); linkNode6.data = 6; linkNode1.next = linkNode2; linkNode2.next = linkNode3; linkNode3.next = linkNode4; linkNode4.next = linkNode5; linkNode5.next = linkNode6; return linkNode1; }
如上代码所示
递归法会逐层确定该节点有没有next节点,若为空,则认定递归到最深层元素。同时将该层节点的next指向父节点,在递归栈中以此类推。
static Node reverseLinkedList(Node node) { if (node == null || node.next == null) { return node; } else { Node headNode = reverseLinkedList(node.next); node.next.next = node; node.next = null; return headNode; } }
上图展示了递归后的效果。 如果注释掉第7行,会发生如上图所示的1、2号节点闭环问题。由于1号节点的next没有置空,依旧指向2号节点,所以遍历时候肯定存在环。
-
单链表反转 遍历法Java实现
2020-04-29 关注 1 浏览1023 1答案
-
递归地反转Java中的链表
2021-02-02 关注 0 浏览127 1答案
-
如何反转单链表
2020-01-28 关注 0 浏览444 1答案
-
编程实现单链表的逆转函数
2022-03-03 关注 0 浏览30 1答案
-
手写代码:反转链表 (Java 版)
2020-01-31 关注 0 浏览735 1答案
-
如下代码是实现反转链表的一部分代码:反转链表为:输入一个链表的头节点,反转...
2022-03-02 关注 0 浏览39 1答案
-
Java,递归地反转数组
2021-01-30 关注 0 浏览88 1答案
-
【不可使用本地IDE】给定一个链表,编程实现链表反转。
2022-03-02 关注 0 浏览41 1答案
-
将长度为n的有序单链表LA与长度为m的有序单链表LB合并为一条有序的单链表...
2022-03-03 关注 0 浏览38 1答案
-
单链表排序
2022-03-03 关注 0 浏览25 1答案