已知一个带头节点的单链表,结点结构为(data,next),假设该链表只给出了头指针l,在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置的结点(k为正整数)。若查找成功,算法
时间: 2023-04-19 17:01:50 浏览: 218
带头结点单链表的逻辑结构-工程应用软件开发技术
如下:
1. 定义两个指针p和q,初始时均指向头节点l。
2. 让指针p先走k步,此时指针q和指针p之间的距离为k。
3. 然后同时移动指针p和指针q,每次移动一步,直到指针p到达链表末尾。
4. 此时指针q所指向的节点即为倒数第k个节点。
算法的时间复杂度为O(n),其中n为链表的长度。
阅读全文