链表逆序用哨兵位头节点

server/2024/10/11 9:22:50/

在C语言中实现链表的逆序,使用哨兵头节点是一种常见的做法。哨兵头节点可以简化代码逻辑,特别是当链表为空时,可以避免空指针异常。下面是一个使用哨兵头节点逆序单链表的C语言实现

示例:

#include <stdio.h>
#include <stdlib.h>// 定义链表节点结构体
typedef struct ListNode {int val;struct ListNode *next;
} ListNode;// 创建新节点
ListNode* createNode(int value) {ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));if (!newNode) {exit(-1); // 分配内存失败,退出程序}newNode->val = value;newNode->next = NULL;return newNode;
}// 逆序链表,使用哨兵头节点
void reverseList(ListNode** headRef) {ListNode* prev = NULL;ListNode* current = *headRef;ListNode* next = NULL;while (current != NULL) {next = current->next;  // 保存下一个节点current->next = prev;  // 当前节点指向前一个节点,实现逆序prev = current;        // 前一个节点移动到当前节点current = next;        // 当前节点移动到下一个节点}*headRef = prev;  // 更新头节点
}// 打印链表
void printList(ListNode* head) {ListNode* temp = head;while (temp != NULL) {printf("%d ", temp->val);temp = temp->next;}printf("\n");
}// 主函数,测试逆序链表功能
int main() {ListNode* head = createNode(1);head->next = createNode(2);head->next->next = createNode(3);head->next->next->next = createNode(4);printf("原始链表:");printList(head);reverseList(&head);printf("逆序后链表:");printList(head);// 释放链表内存ListNode* temp;while (head != NULL) {temp = head;head = head->next;free(temp);}return 0;
}

在这个代码中,我们首先定义了链表节点的结构体ListNode,然后提供了创建新节点的函数createNodereverseList函数用来逆序链表,它使用了一个哨兵头节点,即第一个节点作为prev指针的初始位置,最后将头节点更新为prev指针所指向的节点。printList函数用来打印链表的节点值。

main函数中,我们创建了一个简单的链表,并调用reverseList函数进行逆序,然后打印出逆序后的结果。最后,我们释放了链表占用的内存。

请注意,在实际的项目开发中,还需要对代码进行适当的错误处理和边界条件检查,以确保程序的健壮性。

在C语言中,使用哨兵位头节点(dummy head)来逆序链表是一种常见的技巧,因为它可以简化边界条件的处理。以下是一个使用哨兵位头节点逆序单链表的示例代码:

// 链表节点的结构体定义

typedef struct ListNode {int val;struct ListNode *next;
} ListNode;

// 创建一个新的链表节点

ListNode* createNode(int value) {ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));if (!newNode) {exit(-1); // 分配内存失败,退出程序}newNode->val = value;newNode->next = NULL;return newNode;
}

// 在链表的末尾添加一个新节点

void appendNode(ListNode** headRef, int value) {ListNode* newNode = createNode(value);ListNode* temp = *headRef;if (temp == NULL) {*headRef = newNode;return;}while (temp->next != NULL) {temp = temp->next;}temp->next = newNode;
}

// 逆序链表,使用哨兵位头节点

void reverseList(ListNode** headRef) {ListNode* prev = NULL;ListNode* current = *headRef;ListNode* next = NULL;while (current != NULL) {next = current->next;  // 保存下一个节点current->next = prev;  // 当前节点指向前一个节点prev = current;        // 前一个节点移动到当前节点current = next;        // 当前节点移动到下一个节点}*headRef = prev;  // 更新头节点
}

// 打印链表

void printList(ListNode* head) {ListNode* temp = head;while (temp != NULL) {printf("%d ", temp->val);temp = temp->next;}printf("\n");
}

// 主函数,测试逆序链表功能

int main() {ListNode* head = NULL; // 哨兵位头节点// 向链表中添加元素appendNode(&head, 1);appendNode(&head, 2);appendNode(&head, 3);appendNode(&head, 4);printf("原始链表:");printList(head);// 逆序链表reverseList(&head);printf("逆序后链表:");printList(head);// 释放链表内存ListNode* temp;while (head != NULL) {temp = head;head = head->next;free(temp);}return 0;
}

总代码

#include <stdio.h>
#include <stdlib.h>// 链表节点的结构体定义
typedef struct ListNode {int val;struct ListNode *next;
} ListNode;// 创建一个新的链表节点
ListNode* createNode(int value) {ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));if (!newNode) {exit(-1); // 分配内存失败,退出程序}newNode->val = value;newNode->next = NULL;return newNode;
}// 在链表的末尾添加一个新节点
void appendNode(ListNode** headRef, int value) {ListNode* newNode = createNode(value);ListNode* temp = *headRef;if (temp == NULL) {*headRef = newNode;return;}while (temp->next != NULL) {temp = temp->next;}temp->next = newNode;
}// 逆序链表,使用哨兵位头节点
void reverseList(ListNode** headRef) {ListNode* prev = NULL;ListNode* current = *headRef;ListNode* next = NULL;while (current != NULL) {next = current->next;  // 保存下一个节点current->next = prev;  // 当前节点指向前一个节点prev = current;        // 前一个节点移动到当前节点current = next;        // 当前节点移动到下一个节点}*headRef = prev;  // 更新头节点
}// 打印链表
void printList(ListNode* head) {ListNode* temp = head;while (temp != NULL) {printf("%d ", temp->val);temp = temp->next;}printf("\n");
}// 主函数,测试逆序链表功能
int main() {ListNode* head = NULL; // 哨兵位头节点// 向链表中添加元素appendNode(&head, 1);appendNode(&head, 2);appendNode(&head, 3);appendNode(&head, 4);printf("原始链表:");printList(head);// 逆序链表reverseList(&head);printf("逆序后链表:");printList(head);// 释放链表内存ListNode* temp;while (head != NULL) {temp = head;head = head->next;free(temp);}return 0;
}

在这个代码中,我们首先定义了链表节点的结构体ListNode。然后,我们提供了创建新节点和向链表末尾添加新节点的函数createNodeappendNodereverseList函数用来逆序链表,它使用了一个哨兵头节点prev,并最终将头节点更新为prev指针所指向的节点。printList函数用来打印链表的节点值。

main函数中,我们创建了一个链表,并调用reverseList函数进行逆序,然后打印出逆序后的结果。最后,我们释放了链表占用的内存。

请注意,在实际的项目开发中,还需要对代码进行适当的错误处理和边界条件检查,以确保程序的健壮性。


http://www.ppmy.cn/server/46566.html

相关文章

css样式,点击 箭头方向上下转换

实现效果&#xff1a; 点击切换箭头方向 实现代码 <divclass"modelPart"click"showClick"><div class"modelPart_left"><img:srcaidefalutIconclass"sNodeIcon"><div>{{ selectModel }}</div><div …

Nginx 实战-03-nginx 负载均衡

前言 大家好&#xff0c;我是老马。很高兴遇到你。 我们为 java 开发者实现了 java 版本的 nginx https://github.com/houbb/nginx4j 如果你想知道 servlet 如何处理的&#xff0c;可以参考我的另一个项目&#xff1a; 手写从零实现简易版 tomcat minicat 手写 nginx 系列 …

11.3 冒泡排序

目录 11.3 冒泡排序 11.3.1 算法流程 11.3.2 效率优化 11.3.3 算法特性 11.3 冒泡排序 冒泡排序&#xff08;bubble sort&#xff09;通过连续地比较与交换相邻元素实现排序。这个过程就像气泡从底部升到顶部一样&#xff0c;因此得名冒泡排序。 如图 11-4 所示…

Spring系统学习 - Spring入门

什么是Spring&#xff1f; Spring翻译过来就是春天的意思&#xff0c;字面意思&#xff0c;冠以Spring的意思就是想表示使用这个框架&#xff0c;代表程序员的春天来了&#xff0c;实际上就是让开发更加简单方便&#xff0c;实际上Spring确实做到了。 官网地址&#xff1a;ht…

LabVIEW在高校电力电子实验中的应用

概述&#xff1a;本文介绍了如何利用LabVIEW优化高校电力电子实验&#xff0c;通过图形化编程实现参数调节、实时数据监控与存储&#xff0c;并与Simulink联动&#xff0c;提高实验效率和数据处理能力。 需求背景高校实验室在进行电机拖动和电力电子实验时&#xff0c;通常使用…

基于Springboot驾校预约平台小程序的设计与实现(源码+数据库+文档)

一.项目介绍 系统角色&#xff1a;管理员、教练、学员 小程序(仅限于学员注册、登录)&#xff1a; 查看管理员发布的公告信息 查看管理员发布的驾校信息 查看所有教练信息、预约(需教练审核)、评论、收藏喜欢的教练 查看管理员发布的考试信息、预约考试(需管理…

Python——cv2 判断图像读取内容是否为空

import cv2 pic_path"xxx.jpg" imagecv2.imread(pic_path) if None image:print("图片为空") else:print("图片不为空")

EureKa是什么?

Eureka 是一个源于 Netflix 公司的开源项目&#xff0c;主要用于实现服务注册和服务发现的功能。它是构建分布式系统中的微服务架构的一个关键组件。下面是对 Eureka 的解释&#xff1a; 基本概念 Eureka 是基于 REST 的服务&#xff0c;主要用于管理微服务架构中的服务实例的…