链表的遍历和反转

马谦马谦马谦
马谦马谦马谦
马谦马谦马谦
611
文章
12
评论
2018年3月25日17:33:48 评论

一、链表的遍历

链表的遍历算是十分简单了,从头到尾获取next指针的值,如果next不为0,一直打印。

这是一个链表和双向链表都可以使用的打印方式,但是对于循环链表来说要注意起始节点。

二、链表反转

链表反转在面试中经常会考的问题,总结了一下共有一下几种方式:

  • 修改链表指向实现。
  • 使用栈实现。
  • 递归实现

2.1 修改链表指向

修改节点的流程:

  1. 初始化节点,设置当前修改的节点cur为第一个节点root.getNext()
  2. 如果当前指向的节点cur存在,向下执行修改,否则退出反转。
  3. 备份当前节点的下一个节点。
  4. 修改当前节点的下一个节点为上一个节点。
  5. cur指向备份的下一个节点,继续第二步。

对于双向链表的反转也是一样,只是多了一个指针替换:

2.2 通过栈反转

栈的特点是先进后出,因此通过栈来反转是再合适不过了。

2.3 通过递归反转

如果只需要反向打印列表,通过递归的方式反转也是相当简单,只是当链表过长时可能会导致内存溢出。

也可以直接通过这个方法逆向构造一个链表然后重新赋值root达到在当前对象上反转的目的,把vector改成一个链表对象每次都插入元素在最后。

历史上的今天
三月
25
马谦马谦马谦
  • 本文由 发表于 2018年3月25日17:33:48
  • 转载请务必保留本文链接:https://www.dyxmq.cn/program/code/c-cpp/print-list-and-reverse-list.html
给socket分配随机端口 C/C++

给socket分配随机端口

客户端的socket不需要手动执行bind绑定地址,但这不意味着客户端socket真的不需要绑定端口,实际上是内核它帮我们做了这个操作,在执行connect时,内核发现没有绑定端口,就会自动选择一个合...
vector中emplace_back方法的用途 C/C++

vector中emplace_back方法的用途

在写代码的过程中,CLion提醒我把push_back方法替换成emplace_back方法: 代码中我的想法是使用vector创建一个二维数组,并提前分配好空间,避免后序频繁扩容增加时间复杂度。 e...
宏定义踩坑实战:嵌套调用宏定义 C/C++

宏定义踩坑实战:嵌套调用宏定义

问题背景:在刷题的过程中,要使用min函数,但是线上OJ并没有这个函数。因为一时也想不起它到底属于哪个头文件,所以为了偷懒,顺手就写下了以下宏定义: #define min(x, y) (x) <...
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: