关于序列遍历时索引和元素对齐的简便记忆法则

2022-03-14

链表和数组遍历中索引和元素的对齐问题。

1、基本原则

基本法则是：确定遍历开始时的对应关系，在循环体内，调用next之前，对应关系保持不变，调用next之后，对应关系偏移一位。

2、举例说明

在每K个一组反转链表的问题中，需要计算剩下的元素还有没有K个，有如下代码片段：

tail = pre
for i in range(K):
    tail = tail.next
    if not tail:
        return hair.next
    

以上代码中，起始代码中，tail的指向是这样的：

紫色的是要数K的元素。循环体内执行完tail=tail.next之后，tail就指向了第一个要数的元素，这时i的值是0。由此我们确定了tail和i的对应关系。

要数够K个元素，显然需要循环到最后的i=K-1时，tail仍然要指向一个有效的元素。