循环中有个不变的性质:p一定是第i个结点。循环结束后,若i的值是k,显然得到了所求结点。若值不是k,只有一种可能,即p已经到达NULL。显然,以下三条陈述互为充要条件:
因此,两种写法显然具有等价的不变式,修改后的算法仍然保持一切原有性质,算法等价性成立。