数据结构里面的一个问题

img


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

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

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

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