链表反转的递归和非递归实现方式

红太狼 2022-08-08 05:16 148阅读 0赞

链表反转是数据结构的基本功，主要有递归和非递归两种实现方式。我们一一介绍如下：

# 1. 非递归实现 #

主要包括如下4步：

1）如果head为空，或者只有head这一个节点，return head即可；

2）从头到尾遍历链表，把reversedHead赋值给当前节点的next；

3）当前节点赋值给reversedHead；

4）遍历结束，return reversedHead。

下图试图来辅助说明：

![Center][]

代码如下：

node* reverseList(node* head)
    {
    	if(head == NULL || head->next == NULL)
    		return head; 
    	node* reversedHead = NULL; 
    	node* p = head; 
    
    	while(p != NULL)
    	{
    		node* q = p; 
    		q->next = reversedHead; 
    		reversedHead = q; 
    		p = p->next; 
    	}
    	return reversedHead; 
    }

# 2. 递归实现 #

递归的实现方式主要有4步：

1）如果head为空，或者只有head这一个节点，return head即可；

2）先遍历head->next为首的链表，得到一个头结点newHead；

3）把head赋值给head->next->next， head->next为空；

4）返回newHead。

下图也说明了上述步骤：

![Center 1][]

代码实现如下：

node* reverseList2(node* head)
    {
    	if(head == NULL || head->next == NULL)
    		return head;
    	
    	node* newHead = reversedList2(head->next);
    	head->next->next = head; 
    	head->next = NULL;
    	return newHead; 
    }

[Center]: /images/20220805/fc7c994806034fa6a6bba06ea9a6b116.png
[Center 1]: /images/20220805/c5bb1603ac4f4952939f8492132ec7cb.png

发表评论取消回复

表情：

评论列表（有 0 条评论，148人围观）

还没有评论，来说两句吧...

相关阅读

相关反转链表递归实现

class Solution { public ListNode reverseList(ListNode head) { ...

╰+攻爆jí腚メ/ 2024年04月17日 05:38/ 0 赞/ 36 阅读

相关递归方法反转链表（Java实现）

> class Node{ > int value; > Node next; > public Node(){} > publ

雨点打透心脏的1/2处/ 2023年09月27日 09:16/ 0 赞/ 74 阅读

相关利用递归和非递归的方式实现求字符串长度

![在这里插入图片描述][20210317171927781.png] 求字符串的长度因为在,每一个字符串里面都存在’\\0’,所以这种题的思路就是当==最后这个\\

太过爱你忘了你带给我的痛/ 2022年12月19日 09:28/ 0 赞/ 103 阅读

相关 rust 链表非递归

简单写了一下rust链表的一些基本操作，`append`，`delete`之类的熟悉一下rust之间的借用，和巧用`.take()`方法。 append是用递归的思路，

待我称王封你为后i/ 2022年09月04日 08:55/ 0 赞/ 137 阅读

相关单链表反转- 递归

@Test public void test03() { ListNode listNode = new ListNode(4,

爱被打了一巴掌/ 2022年09月01日 03:18/ 0 赞/ 147 阅读

相关折半查找的递归和非递归实现

折半查找的递归和非递归实现 <pre name="code" class="cpp">include<iostream> using namespace st

墨蓝/ 2022年08月09日 15:53/ 0 赞/ 180 阅读

相关链表反转的递归和非递归实现方式

链表反转是数据结构的基本功，主要有递归和非递归两种实现方式。我们一一介绍如下： 1. 非递归实现主要包括如下4步： 1）如果head为空，

红太狼/ 2022年08月08日 05:16/ 0 赞/ 149 阅读

相关合并两个有序链表——递归实现和非递归实现

先看代码的实现： include<stdio.h> include<stdlib.h> //链表存储结构 typedef stru

待我称王封你为后i/ 2022年08月07日 11:55/ 0 赞/ 148 阅读

相关单链表反转的递归与非递归实现

此题来源于leetcode 206.单链表反转 Difficulty:Easy 在题目中给出了可使用递归与迭代两种算法的提示。因为对递归理解不深刻，首先采用迭代编

忘是亡心i/ 2022年06月09日 00:11/ 0 赞/ 156 阅读

相关 Trie的递归实现和非递归实现

关于Trie: 在计算机科学中，Trie，又称字典树、单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以

傷城~/ 2022年02月22日 01:29/ 0 赞/ 266 阅读