Leetcode-206.反转链表

• 思路概述

  • 利用栈的 先进后出（LIFO） 特性，先顺序遍历链表，把所有节点压入栈；

  • 弹出栈顶节点时正好是原链表的尾节点，依次连接即可得到反转链表。

• 具体步骤

  1. 初始化空栈 st；

  2. 遍历链表 head，将每个节点压入栈中；

  3. 栈顶弹出节点作为新链表头 new_head，并维护一个可移动尾指针 cur；

  4. 每次出栈一个节点：

     • 先断开该节点原来的 next（防止形成环）；

     • 接在新链表尾部 cur.next = node；

     • 移动尾指针 cur = node；

  5. 循环结束后，cur.next = None 并返回 new_head。

复杂度分析

• 时间复杂度：O(n)，遍历一次压栈，一次出栈；

• 空间复杂度：O(n)，栈存储了全部节点引用。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = nextclass Solution:def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:p=headst=[]while p!=None:st.append(p)p=p.nextdummy = ListNode(0)tail = dummywhile st:node=st.pop()tail.next=nodetail=nodetail.next = Nonereturn dummy.next