【算法题】使用递归和非递归实现单向链表的转置

在浏览的进程中有任何问题,欢迎1起交换

邮箱:1494713801@qq.com   

QQ1494713801

 

问题:

给1个单向链表,把它从头到尾反转过来。比如: a -> b -> c ->d 反过来就是 d -> c -> b -> a 

分析:

假定每个node的结构是:

class Node { char value; Node next;}

 

非递归方式代码以下:

1. void reverse(struct Node **list)  

2. {  

3.     struct Node *currentp = *list;  

4.     struct Node *pleft = NULL;  

5.     struct Node *pright = NULL;  

6.       

7.   

8.     while (currentp != NULL) {  

9.         pright = currentp->next;  

10.         currentp->next = pleft;  

11.         pleft = currentp;  

12.         currentp = pright;  

13.     }  

14.     *list = pleft;  

15. } 

递归的方式代码以下:

1. struct Node* recursive_reverse(struct Node *list)  

2. {  

3.     struct Node *head = list;  

4.     struct Node *p = r_reverse(list);  

5.     head->next = NULL;  

6.     return p;  

7. }  

8.   

9. struct Node *r_reverse(struct Node *list)  

10. {  

11.     if (NULL == list || NULL == list->next)   

12.         return list;  

13.     struct Node *p = r_reverse(list->next);  

14.     list->next->next = list;  

15.     return p;  

16. }  

递归的方法实际上是非常巧的,它利用递归走到链表的末端,然后再更新每个node的next 值 (代码倒数第2句)。 在上面的代码中, reverseRest 的值没有改变,为该链表的最后1个node,所以,反转后,我们可以得到新链表的head。

 

单链表相邻元素转置(非递归)

1. struct Node* recursive_reverse(struct Node *list)  

2. {  

3.     struct Node *head = list;  

4.     struct Node *p = r_reverse(list);  

5.     head->next = NULL;  

6.     return p;  

7. }  

8.   

9. struct Node *r_reverse(struct Node *list)  

10. {  

11.     if (NULL == list || NULL == list->next)   

12.         return list;  

13.     struct Node *p = r_reverse(list->next);  

14.     list->next->next = list;  

15.     return p;  

16. }  

4   单链表相邻元素转置(递归)

1. struct Node * recursive_partial_reverse(struct Node *list)  

2. {  

3.     if (NULL == list || NULL == list->next)  

4.         return list;  

5.     struct Node *p = list->next;  

6.     struct Node *node = recursive_partial_reverse(list->next->next);  

7.     list->next->next = list;  

8.     list->next = node;  

9.     return p;  

10. }  

 

参考链接:

http://blog.csdn.net/skylinesky/article/details/760694

 

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » 【算法题】使用递归和非递归实现单向链表的转置

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡