核心数据结构

class ListNode:
    """单链表节点：存一个值 val，存一个指向下一节点的指针 next。"""
    def __init__(self, val: int, next: "ListNode | None" = None):
        self.val = val
        self.next = next


def reverse_list(head: ListNode | None) -> ListNode | None:
    """迭代反转单链表，返回新的头节点。时间 O(n)，额外空间 O(1)。"""
    prev = None            # prev 指向已反转部分的头；初始为空
    cur = head             # cur 指向待处理的当前节点
    while cur is not None:
        nxt = cur.next     # 先存下后继，否则改向后就找不到它了
        cur.next = prev    # 核心：把当前节点的指针翻向前一个节点
        prev = cur         # prev 前进到当前节点
        cur = nxt          # cur 前进到原来的后继
    return prev            # cur 走到空时，prev 即为反转后的头


def to_list(head: ListNode | None) -> list[int]:
    """把链表读成 Python 列表，便于打印验证。"""
    out = []
    while head is not None:
        out.append(head.val)
        head = head.next
    return out


# 构造 1 -> 2 -> 3 -> 4 并反转
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
print(to_list(head))                 # [1, 2, 3, 4]
print(to_list(reverse_list(head)))   # [4, 3, 2, 1]

def is_valid(s: str) -> bool:
    """判断括号串是否合法配对。时间 O(n)，空间 O(n)。"""
    pairs = {")": "(", "]": "[", "}": "{"}   # 右括号 -> 对应的左括号
    stack: list[str] = []                    # 用 list 当栈，存未匹配的左括号
    for ch in s:
        if ch in pairs:                      # 遇到右括号
            # 栈空说明没有左括号可配；栈顶不匹配说明配错了
            if not stack or stack.pop() != pairs[ch]:
                return False
        else:                                # 遇到左括号，压栈等待匹配
            stack.append(ch)
    return not stack                         # 全部配完则栈应为空


print(is_valid("()[]{}"))   # True
print(is_valid("([)]"))     # False：右括号 ) 配到的栈顶是 [，不匹配
print(is_valid("(]"))       # False
print(is_valid("((("))      # False：结束时栈非空，有左括号没配上

import heapq

def top_k_largest(nums: list[int], k: int) -> list[int]:
    """返回最大的 k 个元素。维护大小为 k 的最小堆，时间 O(n log k)。"""
    heap: list[int] = []                 # 最小堆，heapq 默认就是最小堆
    for x in nums:
        if len(heap) < k:
            heapq.heappush(heap, x)      # 还没攒够 k 个，直接入堆
        elif x > heap[0]:                # heap[0] 是当前 k 个里最小的
            heapq.heapreplace(heap, x)   # 弹出最小、压入 x，一步完成 O(log k)
    return sorted(heap, reverse=True)    # 堆内无序，按需排序输出


print(top_k_largest([3, 1, 5, 12, 2, 11, 8], 3))   # [12, 11, 8]
print(top_k_largest([4, 4, 4, 1], 2))              # [4, 4]

def next_greater(nums: list[int]) -> list[int]:
    """对每个元素，求其右侧第一个更大的元素；没有则为 -1。时间 O(n)。"""
    n = len(nums)
    ans = [-1] * n           # 默认右侧无更大元素
    stack: list[int] = []    # 单调递减栈，存的是下标
    for i, x in enumerate(nums):
        # 当前值 x 比栈顶下标处的值大 → x 就是那个元素的下一个更大元素
        while stack and nums[stack[-1]] < x:
            j = stack.pop()  # 弹出被解决的下标
            ans[j] = x       # 记录答案：j 右侧第一个更大的是 x
        stack.append(i)      # x 自己还没找到更大元素，入栈等待
    return ans               # 留在栈里的下标，右侧再无更大元素，保持 -1


print(next_greater([2, 1, 5, 6, 3]))   # [5, 5, 6, -1, -1]
print(next_greater([5, 4, 3, 2, 1]))   # [-1, -1, -1, -1, -1]