秒懂单链表及其反转(reverse)
2024-08-30 13:57:14
什么是链表,这种数据结构是由一组Node组成的,这群Node一起表示了一个序列。链表是最普通,最简单的数据结构(物理地址不连续),它是实现其他数据结构如stack, queue等的基础。
链表比起数组来,更易于插入,删除。
Node可以定义如下:
typedef int element_type;
typedef struct node *node_ptr; struct node {
element_type element;
node_ptr next;
};
另外关于要不要头节点这个问题,我建议加上头节点,理由如下:
1. 没有头节点,删除第一个节点后,不小心就丢失了List
2. 插入头部时,没有个直观的方法。
3. 通常的删除操作,都要先找到前一个节点,如果没有头节点,删除第一个节点就不一样了。
接下来重点实现单链表的反转,这也是常常考到的一个问题,下面是C语言实现:
void list_reverse(LIST L)
{
if (L->next == NULL) return;
node_ptr p = L->next, first = L->next;
while (p != NULL && p->next != NULL) {
node_ptr next_node = p->next;
p->next = next_node->next;
next_node->next = first;
first = next_node;
}
L->next = first;
}
最新文章
- [APUE]不用fcntl实现dup2函数功能
- 关于strlen误用的一点记录
- Windows Internals学习笔记(六)Windows关键系统组件
- 反向Ajax,实现服务器向客户端推送消息
- [ActionScript 3.0] AS3.0 烟雾粒子效果
- tune 06 Database Configuration and I/O Issues
- HTML5新增结构标签
- Django request 常用属性
- spring mvc标准项目结构
- 教你正确地利用Netty建立连接池
- Http 请求头中的 Proxy-Connection
- linux-sfdisk 使用方法
- ThinkPHP3.2 常量参考
- linux 压缩与解压
- Spring+Spring MVC+MyBatis框架集成
- C#的XML文件的读取与写入
- scp的简单记忆方法
- go web framework gin 路由表的设计
- VC++ MFC单文档应用程序SDI下调用glGenBuffersARB(1, &;pbo)方法编译通过但执行时出错原因分析及解决办法:glewInit()初始化的错误
- SqlServer中查看索引的使用情况