链表的遍历和反转

马谦马谦马谦 2018年3月25日17:33:48 发表评论
文章最后编辑于:2018-3-25 17:34:52

一、链表的遍历

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

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

二、链表反转

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

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

2.1 修改链表指向

修改节点的流程:

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

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

2.2 通过栈反转

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

2.3 通过递归反转

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

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

本文共执行43次查询,耗时0.276秒!
马谦马谦马谦

发表评论

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