链表的遍历和反转

马谦马谦马谦
马谦马谦马谦
马谦马谦马谦
608
文章
9
评论
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改成一个链表对象每次都插入元素在最后。

历史上的今天
3月
25
马谦马谦马谦
  • 本文由 发表于 2018年3月25日17:33:48
  • 转载请务必保留本文链接:https://www.dyxmq.cn/program/code/c-cpp/print-list-and-reverse-list.html
C++文件输入输出流fstream的基本用法 C/C++

C++文件输入输出流fstream的基本用法

一、文件流 C++的IO类中定义了三个文件读写流fstream、ifstream以及ofstream,它们都继承于相同的父类istream,通过不同的实现以实现不同的文件流操作。 三者的区别为: if...
C++11中const_cast的真实使用场景 C/C++

C++11中const_cast的真实使用场景

一、const和成员函数的故事 const的用途有以下几种: 修饰全局、局部、成员变量 修饰成员函数 修饰变量的时候const限制了变量在整个程序运行期间都是不能修改的,而修饰成员函数的时候限制函数内...
C++11中的override和final关键字 C/C++

C++11中的override和final关键字

一、前言 昨天在公司做代码扫描,发现很多类似以下的代码都产生了告警,导致扫描不通过: virtual int func() override {} 不通过的原因是:同时使用virtual和overri...
匿名

发表评论

匿名网友 填写信息

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