版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50514593
翻译
反转一个单链表。
原文
Reverse a singly linked list.
分析
我在草纸上以
有了这个图(每次把博客发出去后就会发现图怎么变得这么小了哎!只能麻烦大家放大看或者另存为了,这图命名是
ListNode* reverseList(ListNode* head) {
ListNode* newHead = NULL;
while (head) {
ListNode* nextNode = head->next;
head->next = newHead;
newHead = head;
head = nextNode;
}
return newHead;
}
上面用的是递归,下面就接着来看看如何把递归改写成迭代。他们的共同点无非就是都有值在不停的进行变换更迭,大家回顾一下上图会发现就是这里的
递归转迭代
第一步:先写出迭代的模板,以及设定好的参数。
ListNode* reverseListIter(ListNode* head, ListNode* newHead) {
}
ListNode* reverseList(ListNode* head) {
}
第二步:为第一次迭代设定初始值。如果已经遗忘了的话,请看上面的递归代码,
ListNode* reverseListIter(ListNode* head, ListNode* newHead) {
}
ListNode* reverseList(ListNode* head) {
return reverseListIter(head, NULL);
}
第三步:上面的一二步可以说是通用的,但从第三步开始就要根据特定的递归过程来改写了。首先是判断迭代停止的条件,上面递归过程中停止的条件是
ListNode* reverseListIter(ListNode* head, ListNode* newHead) {
if (head == NULL) return newHead;
}
紧接着递归中有两个初始的赋值,这里也一并复制过来:
ListNode* reverseListIter(ListNode* head, ListNode* newHead) {
if (head == NULL) return newHead;
ListNode* nextNode = head->next;
head->next = newHead;
return reverseListIter(head, newHead);
}
第四步:更新迭代的参数。可以看到递归代码更新方式如下:
newHead = head;
head = nextNode;
你当然也可以直接这样写到迭代中,但既然用了参数,何不把这过程在代码形式上简化一下呢?
ListNode* reverseListIter(ListNode* head, ListNode* newHead) {
if (head == NULL) return newHead;
ListNode* nextNode = head->next;
head->next = newHead;
return reverseListIter(nextNode, head);
}
那么这样就完成了整个迭代的过程了,棒!
有两个地方需要注意一下:
1,一定要记得return。
2,第一行判断后,返回的是newHead。
这是因为当newHead为空时,返回newHead也是返回空;
当newHead不为空时,其则要作为结果返回给reverseList函数。
其实把改写的过程拆解来看是非常容易理解的,希望我的博客能够帮到大家……
代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseListIter(ListNode* head, ListNode* newHead) {
if (head == NULL) return newHead;
ListNode* nextNode = head->next;
head->next = newHead;
return reverseListIter(nextNode, head);
}
ListNode* reverseList(ListNode* head) {
return reverseListIter(head, NULL);
}
};