首页 > 代码库 > 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

                                         此小篇就这么优雅的完成了~  

 

List链表模板类的简单实现(部分方法递归操作)