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

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

1
2
3
4
5
6
7
8
9

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