采纳答案成功!
向帮助你的同学说点啥吧!感谢那些助人为乐的人
老师,你好.目前,我只想得出来有关它的递归终止条件
public Node reverseList(Node head) {
// 如果链表为空或者链表中只有一个元素
if (head == null || head.next == null) {
return head;
}else { //剩下的就不会了..........
return newHead;
}
在写递归逻辑的时候,一个非常重要的原则就是:使用你涉及的递归函数的宏观语意!在回忆一下我在这个课程中介绍的:递归的过程和子函数调用没有任何区别!只不过我们调用的这个子函数是自己这个函数而已。自己这个函数在做什么事情,我们的子函数调用也在做什么事情。只不过传的参数不同!
再回顾一下我们在第五章写的从链表中删除元素的递归算法:
public
ListNode removeElements(ListNode head,
int
val) {
if
(head ==
null
)
// 递归终止条件
return
head;
// 递归调用
head.next = removeElements(head.next, val);
// 此时,我么已经删除了head.next这个链表中所有值为val的元素
// 因为removeElement做的就是这件事情!
// 我们最后处理当前唯一没有处理的head节点的元素
head.val == val ? head.next : head;
请好好体会一下我在课程中所讲的递归的宏观语意。
现在我们看reverseList。同理,reverseList做的事情就是将传入的链表进行反转,返回新的头结点。所以我们调用reverseList(head.next),就会将head.next这个链表进行反转,返回新的头结点。我们剩下要处理的,就剩下head节点了:)
整体,我们有以下代码:
ListNode reverseList(ListNode head) {
|| head.next ==
// 将head.next进行反转,反转后的链表的头结点返回给newHead
ListNode newHead = reverseList(head.next);
// 这里要注意:在链表进行反转以后,head.next仍然指着原先的head.next
// 因为我们在reverseList(head.next)的过程中,没有动head!
// 只不过此时,原先的head.next,同时是对head.next反转的尾节点
// 也就是,现在的head.next,有两个节点的next指着它
//
// 比如:1->2->3->4->5->NULL
// 如果head是2所在的节点的话,我们的这句递归调用,是反转以3为头节点的链表
// 运行后的结果应该为:1->2->3<-4<-5,并且返回了5
// 对以3为头结点的链表进行反转,结果为5->4->3->NULL,新的链表的头结点为5
// 但是由于我们的递归过程和2没有关系,2依然指着3!(2是head,3是head.next)
// 我们下面的任务,就是处理这个2(head)
head.next.next = head;
// 3(head.next)相应的next应该指向2(head)
head.next =
;
// 2(head)的next赋值为空。
newHead;
// 返回newHead}
请再仔细体会一下这个过程。书写递归函数:
1)明确递归函数的宏观语意!说白了就是这个递归函数到底在做什么事情。
2)递归调用的过程,使用这个递归函数,解决一个更小的问题
3)用解决的这个更小的问题的结果,组建当前问题的解(解决了删除head.next中所有的val,如何删除head中所有的val?解决了反转head.next,如何反转head?)
最后,递归算法的编写和设计,确实不容易掌握,需要大量的练习。注意:练习不代表拿100个问题,对每个问题都生想硬看。发现自己没头绪,要马上利用互联网的资源,看别人的解答,别人的分析,体会其中的思路,尽量消化融入到自己的思考路径中。这才是一个学习的过程,进步的过程。一定要善于利用互联网上丰富的资源,为自己所用:)
加油!:)
登录后可查看更多问答,登录/注册
动态数组/栈/队列/链表/BST/堆/线段树/Trie/并查集/AVL/红黑树…
10.6k 16
1.5k 17
1.4k 14
购课补贴联系客服咨询优惠详情
慕课网APP您的移动学习伙伴
扫描二维码关注慕课网微信公众号