数据结构 每日一练:将带头结点的单链表就地逆置(视频讲解两种方法)
2023-12-14 12:51:43
目录
Q:什么是“就地”捏?
A:就是指辅助空间复杂度为O(1),通俗一点来说就是不需要再开辟一块空间来实现算法。
特别说明:?
????????笔者第一次录制视频,言语有些不顺,还望大家见谅!如有错误,请大家指出。
方法一
? ? ? ? 头插法,将头结点摘下来,然后从第一结点开始,一次插入到头结点后面(头插法建立单链表),直到最后一个结点为止。
LinkList Reverse_1(LinkList L)
{
LNode* p, * r; //p为工作指针,r为p的后继,以防止出现断链
p = L->next; //从第一个元素结点开始
L->next = NULL; //先将头结点L的next域置为NULL
while (p != NULL) //依次将元素结点断开
{
r = p->next; //存放p的后继
p->next = L->next; //将p结点插入到头结点之后
L->next = p;
p = r;
}
return L;
}
算法视频分析
?
方法二
????????假设pre,p和r指向3个结点。经过若干操作之后,*pre之前的结点的指针都已经调整完毕,它们的next都指向其原前驱节点。现在令*p结点的next域指向*pre结点,注意到一旦调整指针的指向,*p的后继结点就会断开,因此需要用r来指向原*p的后继结点。注意两点:一是再处理第一个结点时,应将其next域置为NULL ,而不是指向头结点(因为它将作为新表的尾结点);二是处理完最后一个结点后,需要将头结点的指针指向它。
LinkList Reverse_2(LinkList L)
{
LNode* pre, * p = L->next, * r = p->next;
p->next = NULL; //处理第一个结点
while (r != NULL) //r为空的时候说明是最后一个结点
{
pre = p; //依次遍历
p = r;
r = r->next;
p->next = pre; //指针反转
}
L->next = p; //处理最后一个结点
return L;
}
?算法视频分析
文章来源:https://blog.csdn.net/qq_52442214/article/details/132739660
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!