数据结构里面的一个问题

Question

这是大学mooc的一个讨论题,评论区里面意见不一致,个人认为不能这样操作,还请各位指点迷津

Answer 1

循环中有个不变的性质：p一定是第i个结点。循环结束后，若i的值是k，显然得到了所求结点。若值不是k，只有一种可能，即p已经到达NULL。显然，以下三条陈述互为充要条件：

1. p到达NULL
2. i在循环结束时没有到达k
3. 链表不存在第k项

因此，两种写法显然具有等价的不变式，修改后的算法仍然保持一切原有性质，算法等价性成立。