请设计时间和空间上都尽可能高效的算法,在不改变链表的前提下,求链式存储的线性表的倒数第m(>0)个元素
时间: 2023-04-27 15:06:06 浏览: 193
求链式线性表的倒数第K项_C语言_K._
5星 · 资源好评率100%
算法步骤如下:
1. 定义两个指针p和q,初始时都指向链表的头节点。
2. 让指针p先向后移动m-1个位置,此时p指向的节点就是倒数第m个节点的前一个节点。
3. 然后同时移动指针p和q,直到p指向链表的尾节点。此时q指向的节点就是倒数第m个节点。
4. 返回节点q的值即可。
该算法的时间复杂度为O(n),空间复杂度为O(1),是一种时间和空间上都尽可能高效的算法。
阅读全文