链表基础3——单链表的逆置

链表的定义

#include <stdio.h>  
#include <stdlib.h>  
  
typedef struct Node {  
    int data;  
    struct Node* next;  
} Node;  
  
Node* createNode(int data) {  
    Node* newNode = (Node*)malloc(sizeof(Node));  
    if (!newNode) {  
        return NULL;  
    }  
    newNode->data = data;  
    newNode->next = NULL;  
    return newNode;  
}  
  
void printList(Node* head) {  
    Node* current = head;  
    while (current != NULL) {  
        printf("%d ", current->data);  
        current = current->next;  
    }  
    printf("\n");  
}

不带头结点的单向不循环链表的逆置

不带头结点的单向不循环链表的逆置方式主要有以下几种：

  1. 迭代法：
    这种方法使用一个指针遍历链表，同时使用另一个指针指向当前节点的前一个节点。在遍历过程中，每次都将当前节点的next指针指向前一个节点，从而实现链表的逆置。需要注意的是，在逆置过程中，还需要保存下一个要处理的节点，因为逆置后当前节点的next指针会指向前一个节点，从而失去对下一个节点的引用。

  2. 递归法：
    递归法通过递归调用实现链表的逆置。递归的基本思想是：先递归到链表的最后一个节点，然后将该节点的next指针指向它的前一个节点，接着返回前一个节点，继续逆置前面的部分。递归法的好处是代码简洁，但递归深度较大时可能会导致栈溢出。

  3. 栈辅助法：
    这种方法利用栈的后进先出特性来实现链表的逆置。首先将链表中的每个节点依次入栈，然后再依次出栈，并将出栈节点的next指针指向它的前一个出栈节点，从而实现链表的逆置。这种方法需要额外的空间来存储栈中的节点。

  4. 三指针法：
    这种方法使用三个指针，分别指向当前节点、前一个节点和下一个节点。在遍历过程中，先将当前节点的next指针指向前一个节点，然后移动三个指针，继续处理下一个节点。这种方法与迭代法类似，但使用了更多的指针来简化操作。

每种方法都有其特点和适用场景，可以根据具体需求选择合适的方法来实现链表的逆置。在实际应用中，还需要考虑代码的可读性、健壮性和性能等因素。

迭代法

// 迭代法逆置链表  
void reverseListIterative(Node** head) {  
    Node* prev = NULL; // prev指向前一个节点，初始化为NULL  
    Node* current = *head; // current指向当前节点，初始化为头节点  
      
    while (current != NULL) {  
        Node* next = current->next; // next指向下一个节点  
        current->next = prev; // 将当前节点的next指针指向前一个节点，实现逆置  
        prev = current; // 将prev移动到当前节点  
        current = next; // 将current移动到下一个节点  
    }  
      
    *head = prev; // 更新头指针，指向新的头节点（原链表的尾节点）  
}

逐步分解

 

 

到这里循环就结束了

 到这里彻底完成链表的逆置 

递归法

// 递归法逆置链表  
Node* reverseListRecursive(Node* head) {  
    // 递归终止条件：当前节点为空或当前节点的下一个节点为空  
    if (head == NULL || head->next == NULL) {  
        return head;  
    }  
      
    // 递归调用，逆置剩余部分链表，并返回新的头节点  
    Node* newHead = reverseListRecursive(head->next);  
      
    // 处理当前节点，将其指向原来的前一个节点，实现逆置  
    head->next->next = head;  
    head->next = NULL;  
      
    // 返回新的头节点  
    return newHead;  
}
  
// main 函数和其他辅助函数与迭代法相同

递归的思想是将一个大问题分解为若干个更小的子问题来解决。在链表逆置的场景中，我们可以将问题分解为“逆置除头节点外的剩余链表，并将头节点放到逆置后链表的尾部”。

递归函数reverseListRecursive的工作过程如下：

  1. 基本情况（递归终止条件）：
    • 如果链表为空（head == NULL），或者链表只有一个节点（head->next == NULL），那么链表已经逆置完成（或者说，无需逆置），直接返回当前头节点。
  2. 递归步骤：
    • 假设当前头节点head的下一个节点开始的链表部分（即剩余链表）已经通过递归调用reverseListRecursive(head->next)逆置完成，并返回了新的头节点newHead。
  3. 处理当前节点：
    • 在递归调用返回后，newHead指向逆置后链表的头节点。此时，我们需要将当前节点head放到逆置后链表的尾部。
    • 由于head->next现在指向逆置后的链表，我们将head->next->next指向head，这样就将head节点添加到了逆置后链表的尾部。
    • 然后，我们需要将head->next设置为NULL，因为head现在是新链表的最后一个节点。
  4. 返回新头节点：
    • 最后，递归函数返回newHead，即逆置后链表的头节点。

这个过程是一个典型的“自底向上”的递归：我们先递归地逆置剩余部分链表，然后再处理当前节点。递归的每一次调用都处理一个更小的子问题，直到到达基本情况（链表为空或只有一个节点）。

以一个简单的例子来说明：

假设链表为 A -> B -> C -> D。

  • 递归调用reverseListRecursive(D)，D没有下一个节点，返回D。
  • 递归调用reverseListRecursive(C)，它首先递归调用reverseListRecursive(D)得到D，然后将C添加到D的前面，得到D -> C，并返回D作为新头节点。
  • 递归调用reverseListRecursive(B)，它首先递归调用reverseListRecursive(C)得到D -> C，然后将B添加到D -> C的前面，得到C -> D -> B，并返回C作为新头节点。
  • 最后，reverseListRecursive(A)调用reverseListRecursive(B)得到C -> D -> B，然后将A添加到C -> D -> B的前面，得到B -> C -> D -> A，并返回B作为新头节点。

最终，A -> B -> C -> D被逆置为B -> C -> D -> A。

通过这种方式，递归能够逐步地将整个链表逆置。希望这个解释能够更清楚地说明递归是如何实现链表逆置的。

栈辅助法

typedef struct Node {  
    int data;  
    struct Node* next;  
} Node;  
  
typedef struct Stack {  
    Node* top;  
} Stack;  
  
void push(Stack* stack, Node* node) {  
    node->next = stack->top;  
    stack->top = node;  
}  
  
Node* pop(Stack* stack) {  
    if (stack->top == NULL) {  
        return NULL;  
    }  
    Node* node = stack->top;  
    stack->top = stack->top->next;  
    node->next = NULL; // 避免悬挂指针  
    return node;  
}  
  
bool isEmpty(Stack* stack) {  
    return stack->top == NULL;  
}  
  
// 栈辅助法逆置链表  
Node* reverseListWithStack(Node* head) {  
    StackNode* stack = createStack();  
    Node* dummy = createNode(0); // 创建一个哑节点作为新链表的头节点  
    Node* tail = dummy; // tail指向新链表的尾节点  
      
    // 将原链表的节点依次入栈  
    while (head != NULL) {  
        push(&stack, head);  
        head = head->next;  
    }  
      
    // 将栈中的节点依次出栈并连接到新链表上  
    while ((head = pop(&stack)) != NULL) {  
        tail->next = head;  
        tail = head;  
    }  
      
    // 新链表的尾节点指向NULL  
    tail->next = NULL;  
      
    // 返回新链表的头节点（哑节点的下一个节点）  
    return dummy->next;  
}  
  
// 辅助函数和main函数与之前相同

三指针法

// 三指针法逆置链表  
Node* reverseListWithThreePointers(Node* head) {  
    if (head == NULL || head->next == NULL) {  
        return head;  
    }  
      
    Node* prev = NULL;  
    Node* current = head;  
    Node* nextTemp = NULL;  
      
    while (current != NULL) {  
        nextTemp = current->next; // 保存下一个节点  
        current->next = prev; // 反转当前节点的指针  
        prev = current; // prev移动到当前节点  
        current = nextTemp; // current移动到下一个节点  
    }  
      
    return prev; // prev现在指向新的头节点  
}  
  
// ...（其他函数和main函数保持不变）

 逐步分解

 

测验代码

int main() {  
    Node* head = createNode(1);  
    head->next = createNode(2);  
    head->next->next = createNode(3);  
    head->next->next->next = createNode(4);  
      
    printf("Original List: ");  
    printList(head);  
      
    reverseListIterative(&head);  
      
    printf("Reversed List: ");  
    printList(head);  
      
    // 释放链表内存  
    Node* temp;  
    while (head != NULL) {  
        temp = head;  
        head = head->next;  
        free(temp);  
    }  
      
    return 0;  
}

带头结点的单向不循环链表的逆置

对于带头结点的单向不循环链表的逆置，我们依然可以使用递归或迭代的方法。

由于头结点通常不存储数据，而是作为链表的起始标识和方便操作，逆置链表时通常不会涉及头结点的变动。

以下，我将分别解释递归和迭代如何对带头结点的单向不循环链表进行逆置。

递归法

在递归法中，我们关注的是链表的当前节点和它的下一个节点。递归的基本思想是：先递归处理子问题（逆置剩余链表），然后处理当前节点。

 typedef struct ListNode {  
 int val;  
 struct ListNode *next;  
 } ListNode;  
   ListNode* reverseListRecursive(ListNode* head) {  
 // 如果链表为空或只有一个节点（即头结点后面没有节点），则无需逆置  
 if (head == NULL || head->next == NULL) {  
 return head;  
 }  
   // 递归调用，逆置头结点后面的链表部分，并返回新的头节点  
 ListNode* newHead = reverseListRecursive(head->next);  
   // 处理当前头结点，将其next指针指向它的前一个节点  
 head->next->next = head;  
   // 将当前头结点的next指针置为NULL，因为它现在是新链表的最后一个节点  
 head->next = NULL;  
   // 返回新的头节点  
 return newHead;  
 } 

在上面的代码中，递归函数reverseListRecursive接收一个指向头结点的指针head，并返回逆置后链表的新的头结点。注意，由于带头结点，我们不会改变头结点的位置，只会改变头结点后面链表的逆置。

迭代法

迭代法则是通过循环和指针操作来逐步逆置链表。对于带头结点的链表，迭代法通常更加直观和易于理解。

 ListNode* reverseListIterative(ListNode* head) {  
 if (head == NULL || head->next == NULL) {  
 return head;  
 }  
   ListNode* prev = head; // prev初始指向头结点  
 ListNode* curr = head->next; // curr初始指向头结点后的第一个节点  
   // 当curr不为空时，持续进行逆置操作  
 while (curr != NULL) {  
 ListNode* nextTemp = curr->next; // 保存curr的下一个节点  
 curr->next = prev; // 将curr的next指针指向前一个节点，实现逆置  
 prev = curr; // prev向后移动一位  
 curr = nextTemp; // curr向后移动一位  
 }  
   // 最后将头结点的next指向新的头节点  
 head->next = prev;  
   // 返回新的头节点  
 return prev;  
 } 

在这个迭代法中，我们使用三个指针：prev始终指向当前逆置部分的最后一个节点，curr指向待逆置的当前节点，nextTemp用于临时存储curr的下一个节点，以便在逆置当前节点后能够继续迭代。

无论是递归还是迭代法，带头结点的单向不循环链表的逆置操作的关键都在于逐步改变节点的next指针的指向，从而实现链表的逆置。

迭代法通常比递归法在空间效率上更优，因为它不需要递归调用栈的空间。而在时间效率上，两者在平均和最坏情况下通常都是O(n)，其中n是链表的长度。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/546400.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【七 （1）指标体系建设-构建高效的故障管理指标体系】

【七 （1）指标体系建设-构建高效的故障管理指标体系】

目录 文章导航一、故障概述1、故障&#xff1a;2、故障管理&#xff1a; 二、指标体系概述1、指标2、指标体系 三、指标体系构建难点1、管理视角2、业务视角3、技术视角 四、指标体系构建原则1、与战略目标对齐2、综合和平衡3、数据可获得性4、可操作性5、具体和可衡量6、参与和…
阅读更多...
Windows10为Git Bash添加文件传输命令rsync（详细图文配置）

Windows10为Git Bash添加文件传输命令rsync（详细图文配置）

文章目录 1. 安装git bash2. 下载所需要的4个包3. 下载解压包的软件4. 复制每个包下面的usr到git安装目录下4.1 所遇问题4.2 解决 5. 安装完成6. 需要注意 Windows上要使用 rsync命令上传或下载文件&#xff0c;需要使用git bash&#xff0c;git bash没有rsync&#xff0c;需要…
阅读更多...
盘点2024年最新可用免费云服务器

盘点2024年最新可用免费云服务器

随着云计算技术的快速发展&#xff0c;越来越多的企业和个人开始使用云服务器来满足各种业务需求。云服务器作为云计算的核心服务之一&#xff0c;以其弹性扩展、按需付费等特点受到广泛关注。本文将为大家盘点2024年最新可用免费云服务器&#xff0c;助力大家轻松上云&#xf…
阅读更多...
Problem #8 [Easy]

Problem #8 [Easy]

This problem was asked by Google. A unival tree (which stands for “universal value”) is a tree where all nodes under it have the same value. Given the root to a binary tree, count the number of unival subtrees. For example, the following tree has 5 un…
阅读更多...
【c 语言】声明了一个指针，会给指针分配内存吗？

【c 语言】声明了一个指针，会给指针分配内存吗？

&#x1f388;个人主页&#xff1a;豌豆射手^ &#x1f389;欢迎 &#x1f44d;点赞✍评论⭐收藏 &#x1f917;收录专栏&#xff1a;C语言 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共同学习、交流进步&…
阅读更多...
借力社交裂变，Xinstall助你实现用户快速增长

借力社交裂变，Xinstall助你实现用户快速增长

在数字化时代&#xff0c;社交裂变已成为品牌获取新用户、扩大影响力的关键手段。然而&#xff0c;如何有效利用社交裂变&#xff0c;实现用户快速增长&#xff0c;却是许多品牌面临的挑战。今天&#xff0c;我们将为大家介绍一个强大的社交裂变引擎——Xinstall&#xff0c;它…
阅读更多...
状态模式【行为模式C++】

状态模式【行为模式C++】

1.概述 状态模式是一种行为设计模式&#xff0c; 让你能在一个对象的内部状态变化时改变其行为&#xff0c; 使其看上去就像改变了自身所属的类一样。 2.结构 State(抽象状态类)&#xff1a;定义一个接口用来封装与上下文类的一个特定状态相关的行为&#xff0c;可以有一个或多…
阅读更多...
【Linux C | 多线程编程】线程同步 | 互斥量(互斥锁)介绍和使用

【Linux C | 多线程编程】线程同步 | 互斥量(互斥锁)介绍和使用

&#x1f601;博客主页&#x1f601;&#xff1a;&#x1f680;https://blog.csdn.net/wkd_007&#x1f680; &#x1f911;博客内容&#x1f911;&#xff1a;&#x1f36d;嵌入式开发、Linux、C语言、C、数据结构、音视频&#x1f36d; ⏰发布时间⏰&#xff1a; 本文未经允许…
阅读更多...
MoneyPrinterTurbo-利用AI大模型，一键生成高清短视频

MoneyPrinterTurbo-利用AI大模型，一键生成高清短视频

MoneyPrinterTurbo-利用AI大模型&#xff0c;一键生成高清短视频 在今天的信息爆炸的时代&#xff0c;短视频已经成为最受欢迎的信息传递方式之一。无论是分享生活瞬间&#xff0c;还是传递重要信息&#xff0c;短视频都是最直观&#xff0c;最具影响力的手段。但是&#xff0…
阅读更多...
量子城域网系列（四）：几种典型的量子密钥分发网络组网方案

量子城域网系列（四）：几种典型的量子密钥分发网络组网方案

通过之前的文章&#xff0c;我们对点对点的量子保密通信网络有了直观的认识&#xff0c;也知道了量子保密通信系统就是利用量子密钥分发产生的无条件安全量子密钥作为系统安全性保证。所以在实际应用中&#xff0c;一个通信网络如果想实现量子加密&#xff0c;就需要建设量子密…
阅读更多...
12-项目部署_持续集成

12-项目部署_持续集成

项目部署_持续集成 1 今日内容介绍 1.1 什么是持续集成 持续集成&#xff08; Continuous integration &#xff0c; 简称 CI &#xff09;指的是&#xff0c;频繁地&#xff08;一天多次&#xff09;将代码集成到主干 持续集成的组成要素 一个自动构建过程&#xff0c; 从…
阅读更多...
【Linux C | 多线程编程】线程同步 | 总结条件变量几个问题

【Linux C | 多线程编程】线程同步 | 总结条件变量几个问题

&#x1f601;博客主页&#x1f601;&#xff1a;&#x1f680;https://blog.csdn.net/wkd_007&#x1f680; &#x1f911;博客内容&#x1f911;&#xff1a;&#x1f36d;嵌入式开发、Linux、C语言、C、数据结构、音视频&#x1f36d; ⏰发布时间⏰&#xff1a; 本文未经允许…
阅读更多...
PHPStudy（小皮）切换PHP版本PDO拓展失效的问题

PHPStudy（小皮）切换PHP版本PDO拓展失效的问题

因为要看一个老项目&#xff0c;PHP版本在8.0以上会报错&#xff0c;只能切换到7.2&#xff0c;但又遇到了PDO没开启的问题。 PHPStudy上安装的PHP7.2是需要自己配置一下的&#xff0c;里面php.ini文件是空的&#xff0c;需要将php.ini-development改成php.ini&#xff0c;对于…
阅读更多...
VSCode插件分享--免费的ER工具

VSCode插件分享--免费的ER工具

首先在VSCode里面下载插件 再将插件导入后&#xff0c;添加文本修改后缀名&#xff08;将后缀名修改为.drawio&#xff09;就可以使用了
阅读更多...
【个人博客搭建】（1）项目创建

【个人博客搭建】（1）项目创建

1、打开vs2022&#xff0c;创建新项目。筛选一下条件&#xff0c;找到ASP.NET Core Web API 2、按照配置输入自己的项目名称和解决方案名称&#xff0c;以及项目路径 3、接下来就可以选择框架了&#xff0c;我这里选用net8版本&#xff0c;也可以选用net6&#xff0c;都是长期支…
阅读更多...
【Sentinel的限流使用】⭐️SpringBoot整合Sentinel实现Api的限流

【Sentinel的限流使用】⭐️SpringBoot整合Sentinel实现Api的限流

目录 前言 一、Sentinel下载 二、SpringBoot 整合 Sentinel 三、流控规则 章末 前言 小伙伴们大家好&#xff0c;上次使用OpenFeign时用到了 Hystrix实现熔断和限流的功能&#xff0c;但是发现该工具已经停止维护了&#xff0c;于是想到了Spring Cloud Alibaba开发的Sentin…
阅读更多...
【企业动态】瑞芯微高级业务总监来访东胜物联，共探新能源汽车市场合作

【企业动态】瑞芯微高级业务总监来访东胜物联，共探新能源汽车市场合作

近日&#xff0c;瑞芯微高级业务总监阙金珍一行来访东胜物联参观交流&#xff0c;并就深化合作进行讨论。 东胜物联与瑞芯微建有长期稳固的合作关系&#xff0c;基于RK3588、RK3399、RK3568等处理器&#xff0c;推出了多款嵌入式核心硬件产品&#xff0c;包括核心板、网关等&a…
阅读更多...
【报错】TypeError: Cannot read property ‘meta‘ of undefined

【报错】TypeError: Cannot read property ‘meta‘ of undefined

&#x1f608;解决思路 首先这里很明显我们能看到是缺少该参数&#xff1a;meta。 但是经过查找后发现和该参数无关。 &#x1f608;解决方法 后来我上网搜了下&#xff0c;网上的回答大部分偏向于是package.json这个文件中的tabBar.list数组对象只有一条的问题。 网上的大…
阅读更多...
【学习笔记十一】EWM上架目标仓位确定过程及配置

【学习笔记十一】EWM上架目标仓位确定过程及配置

一、EWM确定目标区域概述 1.EWM从仓库处理类型获取源仓库类型&#xff08;Source storage type&#xff09;和源仓位&#xff08;Source Bin&#xff09;2.EWM根据仓库类型&#xff08;storage type&#xff09;、仓库分区&#xff08;storage section&#xff09;和上架策略&a…
阅读更多...
Mamba论文笔记

Mamba论文笔记

Mamba论文 结合序列建模任务通俗地解释什么是状态空间模型&#xff1f;创新点和贡献 为什么Mamba模型擅长捕获long range dependencies&#xff1f; 结合序列建模任务通俗地解释什么是状态空间模型&#xff1f; 状态空间模型&#xff08;State Space Model, SSM&#xff09;是…
阅读更多...
最新文章

Copyright @ 2022~2023