【算法題】使用遞歸和非遞歸實(shí)現(xiàn)單向鏈表的轉(zhuǎn)置

在瀏覽的進(jìn)程中有任何問(wèn)題，歡迎1起交換

郵箱：1494713801@qq.com   

QQ：1494713801

問(wèn)題：

給1個(gè)單向鏈表，把它從頭到尾反轉(zhuǎn)過(guò)來(lái)。比如： a -> b -> c ->d 反過(guò)來(lái)就是 d -> c -> b -> a 。

分析：

假定每個(gè)node的結(jié)構(gòu)是：

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. }  

遞歸的方法實(shí)際上是非常巧的，它利用遞歸走到鏈表的末端，然后再更新每個(gè)node的next 值 (代碼倒數(shù)第2句)。 在上面的代碼中， reverseRest 的值沒(méi)有改變，為該鏈表的最后1個(gè)node，所以，反轉(zhuǎn)后，我們可以得到新鏈表的head。

單鏈表相鄰元素轉(zhuǎn)置（非遞歸）

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   單鏈表相鄰元素轉(zhuǎn)置（遞歸）

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

生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)