写点什么

在没有递归的情况下如何反转单链表?

作者:InfoQ IT百科
  • 2022 年 4 月 24 日
  • 本文字数:546 字

    阅读完需:约 2 分钟

在没有递归的情况下如何反转单链表?


借助栈


借助于栈的先进后出的特点。先从头到尾遍历链表,然后把遍历的结果放入栈中(先进后出),最后输出栈,这样利用栈就实现了从尾到头输出链表元素。Python 实现:

class Solution:    def reversePrint(self, head: ListNode) -> List[int]:            if not ListNode:            return n        stack = []  # 模拟栈        while head:           stack.append(head.val)           head = head.next        return stack[::-1]
复制代码


时间复杂度 O(n):n 是链表的长度,遍历整个链表

空间复杂度 O(n):额外存储结点数组空间


利用额外空间


如果借助于额外的空间的话,我们借助于一个列表。可以先把原链表遍历一遍,进行反转,反转后再打印输出。Python 实现代码如下:

class Solution:    def reversePrint(self, head: ListNode) -> List[int]:    
cur, pre = head, None while cur: temp = cur.next cur.next = pre pre = cur cur = temp res = [] while pre: res.append(pre.val) pre = pre.next return res
复制代码


时间复杂度 O(n):n 是链表的长度,遍历这个链表

空间复杂度 O(n):额外存储结点数组空间

用户头像

还未添加个人签名 2021.04.12 加入

还未添加个人简介

评论

发布
暂无评论
在没有递归的情况下如何反转单链表?_InfoQ IT百科_InfoQ写作社区