请设计时间和空间上都尽可能高效的算法,在不改变链表的前提下,求链式存储的线性表的倒数第m(>0)个元素。
时间: 2023-05-25 16:06:56 浏览: 31
求链式线性表的倒数第K项_C语言_K._
5星 · 资源好评率100%
算法思路:
1. 定义两个指针p和q,p先移动m个节点。
2. 同时移动p和q,直到p指向末尾节点。此时q所指节点即为倒数第m个节点。
算法实现:
```
ListNode* findLastKthNode(ListNode* head, int m) {
if (!head || m < 1) return nullptr;
ListNode* p = head;
ListNode* q = head;
// p指向第m个节点
while (m > 1 && p) {
p = p->next;
m--;
}
if (!p) return nullptr;
// p和q同时移动,直到p指向末尾节点
while (p->next) {
p = p->next;
q = q->next;
}
return q;
}
```
算法分析:
时间复杂度为O(n),其中n为链表长度。
空间复杂度为O(1)。
阅读全文