首页 > 代码库 > List链表模板类的简单实现(部分方法递归操作)
List链表模板类的简单实现(部分方法递归操作)
善哉。
此篇博客,旨在剖析下操作单链表时的递归思想。望各位施主笑纳。
1. 递归删除结点
* 空链表 - 直接返回
* 非空,若未找到待删除元素,递归。若找到,删除节点,返回尾链头
* 回溯,衔接形成新链
1 _Node* myErase_R(const Object& elem, _Node* curr){ 2 //空链 或 无此元素 3 if (curr == NULL) return NULL; 4 5 if (curr->elem == elem){ 6 _Node* tmp = curr->next; 7 delete curr; 8 return tmp; 9 } 10 11 curr->next = myErase_R(elem, curr->next); 12 return curr; 13 }
2. 递归逆置
操作链表的递归思想,大体上是基于用递归将链表分割成多个分结点,当找到符合条件的结点时,进行操作后回溯。
链表逆置的符合条件结点是尾结点,操作是逆置next指针。
思路明朗后,便可模仿链表递归删除的方法,实现递归逆置链表。
1 void myReverse_R(_Node*& curr){ 2 //空链表 3 if (curr == NULL) return ; 4 5 //将链表分割 ->|___|(first) ->|___|->|___|->|___| ... (rest) 6 _Node* first = curr; 7 _Node* rest = first->next; 8 9 //递归终止条件 10 if (rest == NULL) 11 return ; 12 13 myReverse_R(rest); 14 15 //回溯 逆置 16 first->next->next = first; 17 first->next = NULL; 18 19 //改变链头 20 curr = rest; 21 }
下面给出测试代码。
1 void myReverse_R(_Node*& curr){ 2 //空链表 3 if (curr == NULL) return ; 4 5 //将链表分割 ->|___|(first) ->|___|->|___|->|___| ... (rest) 6 _Node* first = curr; 7 _Node* rest = first->next; 8 9 //递归终止条件 10 if (rest == NULL) 11 return ; 12 13 myReverse_R(rest); 14 15 //回溯 逆置 16 first->next->next = first; 17 first->next = NULL; 18 19 //改变链头 20 curr = rest; 21 }
此小篇就这么优雅的完成了~
List链表模板类的简单实现(部分方法递归操作)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。