在没有递归的情况下如何反转单链表？
借助栈
借助于栈的先进后出的特点。先从头到尾遍历链表，然后把遍历的结果放入栈中（先进后出），最后输出栈，这样利用栈就实现了从尾到头输出链表元素。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)：额外存储结点数组空间
评论