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

红太狼 2022-08-08 05:16 224阅读 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 条评论，224人围观）

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

相关阅读

相关反转链表递归实现

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

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

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

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

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

相关 LeetCode：反转链表 (递归)（java）

题目描述: 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->

布满荆棘的人生/ 2023年07月16日 11:55/ 0 赞/ 1 阅读

相关递归和非递归分别实现strlen

1.递归方法实现 include<stdio.h> include<stdlib.h> int Strlen(char str[]){

谁践踏了优雅/ 2023年06月16日 03:55/ 0 赞/ 33 阅读

相关 rust 链表非递归

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

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

相关单链表反转- 递归

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

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

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

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

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

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

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

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

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

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

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

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

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

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