LeetCode 206 Reverse Linked List(反转链表)(Linked List)(四步将递归改写成迭代)(*)

简介: 版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50514593 翻译反转一个单链表。
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50514593

翻译

反转一个单链表。

原文

Reverse a singly linked list.

分析

我在草纸上以 1,2,3,4 为例,将这个链表的转换过程先用描绘了出来(当然了,自己画的肯定不如博客上面精致):

这里写图片描述

有了这个图(每次把博客发出去后就会发现图怎么变得这么小了哎!只能麻烦大家放大看或者另存为了,这图命名是 1400X600 的),那么代码也就自然而然的出来了:

ListNode* reverseList(ListNode* head) {
    ListNode* newHead = NULL;
    while (head) {
        ListNode* nextNode = head->next;
        head->next = newHead;
        newHead = head;
        head = nextNode;
    }
    return newHead;
}

上面用的是递归,下面就接着来看看如何把递归改写成迭代。他们的共同点无非就是都有值在不停的进行变换更迭,大家回顾一下上图会发现就是这里的 head newHead 。所以接下来就把这两个值作为迭代循环的参数。

递归转迭代

第一步:先写出迭代的模板,以及设定好的参数。

ListNode* reverseListIter(ListNode* head, ListNode* newHead) {

}

ListNode* reverseList(ListNode* head) {

}

第二步:为第一次迭代设定初始值。如果已经遗忘了的话,请看上面的递归代码, newHead 一开始是等于 NULL 的,所以增加代码如下。

ListNode* reverseListIter(ListNode* head, ListNode* newHead) {

}

ListNode* reverseList(ListNode* head) {
    return reverseListIter(head, NULL);
}

第三步:上面的一二步可以说是通用的,但从第三步开始就要根据特定的递归过程来改写了。首先是判断迭代停止的条件,上面递归过程中停止的条件是 head 为空,这里照搬。

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,一定要记得return2,第一行判断后,返回的是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);
    }
};
目录
相关文章
|
4月前
|
Java
力扣经典150题第六十题:反转链表 II
力扣经典150题第六十题:反转链表 II
27 1
|
5月前
|
SQL 算法 数据可视化
LeetCode题目92:反转链表ll 【python 递归与迭代方法全解析】
LeetCode题目92:反转链表ll 【python 递归与迭代方法全解析】
|
6月前
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
53 1
|
5月前
|
Java 索引
Java List实战:手把手教你玩转ArrayList和LinkedList
【6月更文挑战第17天】在Java中,ArrayList和LinkedList是List接口的实现,分别基于动态数组和双向链表。ArrayList适合索引访问,提供快速读取,而LinkedList擅长插入和删除操作。通过示例展示了两者的基本用法,如添加、访问、修改和删除元素。根据场景选择合适的实现能优化性能。
51 0
|
5月前
|
Java 开发者 索引
Java List全攻略:从ArrayList到LinkedList,一网打尽!
【6月更文挑战第17天】Java List详解:ArrayList依赖动态数组,擅长随机访问和遍历,适合少次插入删除;LinkedList基于双向链表,插入删除高效,尤其在头尾操作,但随机访问慢。选择取决于应用场景,理解特性以优化代码。探索ArrayList与LinkedList,提升编程效率!
61 0
|
5月前
|
Java 索引
那些年,我们追过的Java List——ArrayList与LinkedList的爱恨情仇
【6月更文挑战第17天】ArrayList与LinkedList,Java List接口的双子星,各有千秋。ArrayList基于数组,随机访问快速,但插入删除慢;LinkedList用链表实现,插入删除高效,但索引访问慢。两者在爱恨情仇中教会我们权衡选择,成为编程旅程中难忘的记忆。 ```
26 0
|
5月前
|
存储 Java C++
Java List大揭秘:ArrayList vs LinkedList,谁才是真正的王者?
【6月更文挑战第17天】ArrayList和LinkedList是Java中实现List接口的两种方式。ArrayList基于动态数组,适合随机访问和遍历,内存紧凑,但插入删除元素特别是在中间时效率低。LinkedList以双向链表实现,擅长任意位置的插入删除,内存管理灵活,迭代高效,但随机访问性能差。选择使用哪种取决于具体应用场景。
38 0
|
5月前
|
Java
JavaSE——集合框架一(4/7)-List系列集合:LinkedList集合的底层原理、特有方法、队列、栈
JavaSE——集合框架一(4/7)-List系列集合:LinkedList集合的底层原理、特有方法、队列、栈
46 0
|
6月前
题目----力扣--反转链表
题目----力扣--反转链表
31 0
|
5月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表

热门文章

最新文章