1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

# 外部循环：控制有多少组 k 个节点可以被反转。
# 循环次数为链表总节点数 // k，表示可以反转的完整 k 个节点组数。
# 每一轮循环会反转一组 k 个节点。
for _ in range(cnt // k):
    # 内部循环：执行 k-1 次头插法操作，从而反转当前 k 个节点。
    # 为什么是 k-1 次？因为我们需要将当前组的第 2 到第 k 个节点，
    # 依次“移动”（通过头插法）到第 1 个节点的前面。
    # 第一次头插法移动第 2 个节点，第二次移动第 3 个节点...
    # 第 k-1 次头插法移动第 k 个节点。
    for _ in range(k - 1):
        # nxt: 指向 cur 节点的下一个节点。
        #      在头插法中，nxt 是我们要从链表中“摘出来”并移动到 pre.next 位置的节点。
        nxt = cur.next

        # cur.next = nxt.next:
        #      将 cur 节点的 next 指向 nxt 节点的下一个节点。
        #      这步操作是为了“跳过” nxt 节点，将 cur 暂时连接到 nxt 之后。
        #      例如：pre -> cur -> nxt -> rest
        #      执行后：pre -> cur ----> rest (nxt 节点暂时脱离 cur 的链条)
        cur.next = nxt.next

        # nxt.next = pre.next:
        #      将 nxt 节点的 next 指向 pre.next。
        #      pre.next 是当前反转组的第一个节点（即 cur）。
        #      将 nxt 插入到 pre.next 的前面，就是实现了头插法。
        #      例如：pre -> cur, nxt -> cur (nxt 的 next 指向 cur)
        #      执行后：nxt -> cur
        nxt.next = pre.next

        # pre.next = nxt:
        #      将 pre.next 指向 nxt。
        #      至此，nxt 节点已经被成功地插入到了 pre 之后，并且是这组反转节点的新头部。
        #      例如：pre -> nxt -> cur
        pre.next = nxt

    # 外部循环更新：
    # 在内部循环结束后，当前反转的 k 个节点已经完成反转，
    # pre 仍然指向这组反转节点的前一个节点（也就是 dummy 或上一组的反转节点）。
    # cur 节点此时指向的是这组反转节点的最后一个节点（也就是原来这组的第一个节点）。
    #
    # pre, cur = cur, cur.next:
    #      将 pre 更新为当前反转组的最后一个节点 (也就是原来的 cur)。
    #      将 cur 更新为下一组需要反转的第一个节点 (也就是原来 cur.next 的值)。
    #      这样，pre 和 cur 就准备好处理下一组 k 个节点的反转了。
    pre, cur = cur, cur.next

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

# 递归反转链表函数：
# 功能：反转从 head 开始，到 tail（不包含 tail）的链表部分
#       返回反转后的链表头节点 (也就是原链表从 head 到 tail 之间最后一个节点)
# head: 当前递归段的起始节点
# tail: 当前递归段的结束标记节点（即要反转的范围的下一个节点）
#       tail 节点本身不参与反转，仅作为结束标记
def reverse(self, head, tail):
    # --- 基本情况 (Base Cases) ---
    # 当我们处理的链表段为空，或者只剩一个有效节点（加上 tail 标记）时，递归停止

    # 情况 1: head == tail
    #   - 如果 head 和 tail 指向同一个节点，意味着我们要反转的区间是空的
    #   - 例如，如果原链表是 A -> B -> C，我们要反转 B 到 C (head=B, tail=C)
    #     第一次递归：reverse(B, C)
    #     第二次递归：reverse(C, C)此时 head == tail，返回 C
    #   - 或者，如果链表是 A -> B，我们要反转 A 到 B (head=A, tail=B)
    #     第一次递归：reverse(A, B)
    #     这种情况也包括在情况 2 中

    # 情况 2: head.next == tail
    #   - 如果 head 的下一个节点就是 tail，说明要反转的链表段只包含 `head`
    #   - 例如，链表是 A -> B -> C -> D
    #     我们要反转 B 到 D (head=B, tail=D)
    #     第一次递归：reverse(B, D)
    #     第二次递归：reverse(C, D)此时 head=C, head.next=D
    #   - 在这种情况下，`head` (节点 C) 就是反转后的这部分的头节点
    #     直接返回 `head`，表示反转完成
    if head == tail or head.next == tail:
        return head

    # --- 递归步骤 (Recursive Step) ---
    # 核心思想：head 被插到的是递归调用 reverse(head.next, tail) 
    #         所返回的那个反转链表段的最前面

    # 1. 递归调用：先反转 `head` 后面的部分 (`head.next` 到 `tail`)
    #    - `self.reverse(head.next, tail)`: 这一步会返回反转后的链表段的头节点
    #      假设链表是 1 -> 2 -> 3 -> 4 -> 5, 我们要反转 1 到 5 (head=1, tail=5)
    #      递归调用会先处理 2 -> 3 -> 4 -> 5
    #      最终，`reverse(2, 5)` 会返回节点 4
    #.     并且链表段 2 -> 3 -> 4 被反转成 4 -> 3 -> 2
    #    - `p` 接收这个返回的头节点（节点 4）
    p = self.reverse(head.next, tail)

    # 2. 执行头插法：将 `head` 插入到 `p` 指向的反转链表的前面
    #    - `head.next.next = head`:
    #      - `head.next` 是当前节点 `head` 的直接后继（在递归调用前）
    #        在递归返回后，`head.next` 实际上是反转后的链表段的第一个节点
    #        所以，这一行代码的意思是：将 `p` 的 `next` 指针指向 `head`
    #      - 以 1 -> 2 -> 3 -> 4 -> 5 (head=1, tail=5) 为例：
    #        递归后，链表是 4 -> 3 -> 2，p 指向 4head 是 1
    #        head.next 是 2
    #        head.next.next = head  =>  2.next = 1
    #        此时链表结构变为：4 -> 3 -> 2 -> 1
    head.next.next = head

    # 3. 更新 `head` 的 `next` 指针：
    #    - `head.next = tail`:
    #      - `head` (节点 1) 是当前处理的链表段的最后一个节点
    #      - 它的 `next` 指针需要指向我们传入的 `tail` 标记
    #      - 以 1 -> 2 -> 3 -> 4 -> 5 (head=1, tail=5) 为例：
    #        head.next = tail  =>  1.next = 5
    #        链表结构变为：4 -> 3 -> 2 -> 1 -> 5
    head.next = tail

    # 4. 返回 `p`:
    #    - `p` 是反转后的链表段的头节点
    #      `p` 是原链表 `head.next` 到 `tail` 之间的最后一个节点
    #    - 这个返回值会被上一层的递归调用接收，用于继续执行头插法
    #    - 例如，在 1 -> 2 -> 3 -> 4 -> 5 的例子中，reverse(1, 5) 返回 p (节点 4)
    #      它才是整个 1 -> 5 区间的反转后的头节点
    return p

1
2
3
4
5
6
7
8
9

# 方法一：从 dummy 节点开始计数
# idx: 指针，从 dummy 开始。
# cnt: 计数器，从 0 开始。
# 循环条件：idx.next。这意味着 idx 会移动到链表的最后一个节点，然后停止。
#     因为它要访问 idx.next，所以 idx 本身不能是链表的最后一个节点。
# 效果：这种方法遍历了链表中所有实际存在的节点。
idx, cnt = dummy, 0
while idx_from_dummy.next:
    idx_from_dummy, cnt = idx_from_dummy.next, cnt + 1

1
2
3
4
5
6
7
8
9

# 方法二：从 head 节点开始计数
# idx: 指针，从 head 开始。
# cnt: 计数器，从 0 开始。
# 循环条件：idx。这意味着 idx 会一直移动，直到它本身变成 None。
#     它会遍历到链表的最后一个节点，并将 idx 移动到 None。
# 效果：这种方法同样遍历了链表中所有实际存在的节点。
idx_from_head, cnt = head, 0
while idx_from_head:
    idx_from_head, cnt = idx_from_head.next, cnt + 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def __init__(self):
        self.res = -float('inf')
    def pathSum(self, root):
        if not root: return 0
        left = max(self.pathSum(root.left), 0)
        right = max(self.pathSum(root.right), 0)
        self.res = max(self.res, left+right+root.val)
        return max(left, right)+root.val
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.pathSum(root)
        return self.res

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

while j < k:
    tmp = a[i] + a[j] + a[k]
    if not tmp:
        res.append([a[i], a[j], a[k]])
        while j < k and a[j] == a[j+1]: j += 1
        while j < k and a[k] == a[k-1]: k -= 1
        j, k = j + 1, k - 1
    elif tmp > 0:
        k -= 1
    else:
        j += 1

1
2
3
4

for _, val in enumerate(nums):
    cur_sum = max(val, val+cur_sum)
    max_sum = max(max_sum, cur_sum)
return max_sum

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

DIRS = (0, 1), (1, 0), (0, -1), (-1, 0)  # 右下左上

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        m, n = len(matrix), len(matrix[0])
        size = m * n
        ans = []
        i, j, di = 0, -1, 0  # 从 (0, -1) 开始
        while len(ans) < size:
            dx, dy = DIRS[di]
            for _ in range(n):  # 走 n 步（注意 n 会减少）
                i += dx
                j += dy  # 先走一步
                ans.append(matrix[i][j])  # 再加入答案
            di = (di + 1) % 4  # 右转 90°
            n, m = m - 1, n  # 减少后面的循环次数（步数）
        return ans