7-1 求链式线性表的倒数第k项 (20 分)
时间: 2023-06-05 10:47:19 浏览: 173
链式线性表的倒数第k项可以通过双指针法来实现。首先定义两个指针p和q,让它们都指向链表的头节点。然后让q指针先向后移动k个位置,接着p和q指针同时向后移动,直到q指针到达链表的末尾。此时p指针所指向的节点就是链表的倒数第k项。
具体实现过程如下:
1. 定义两个指针p和q,让它们都指向链表的头节点。
2. 让q指针先向后移动k个位置。
3. 然后p和q指针同时向后移动,直到q指针到达链表的末尾。
4. 返回p指针所指向的节点即可。
需要注意的是,在移动指针时需要判断链表是否为空,以及k的值是否大于链表的长度。如果链表为空或者k的值大于链表的长度,则无法找到倒数第k项,需要进行相应的处理。
相关问题
7-3 求链式线性表的倒数第k项 (20 分)
链式线性表的倒数第k项可以通过双指针法来实现。首先定义两个指针p和q,初始时p和q都指向链表的头结点。然后让q指针先向后移动k-1个位置,此时p和q之间的距离为k。接着同时移动p和q指针,直到q指针指向链表的尾结点。此时p指针所指向的节点就是链表的倒数第k项。
具体实现可以参考下面的代码:
```
ListNode* findKthToTail(ListNode* head, int k) {
if (head == nullptr || k <= 0) {
return nullptr;
}
ListNode* p = head;
ListNode* q = head;
for (int i = 0; i < k - 1; i++) {
if (q->next != nullptr) {
q = q->next;
} else {
return nullptr;
}
}
while (q->next != nullptr) {
p = p->next;
q = q->next;
}
return p;
}
```
求链式线性表的倒数第k项 (20 分)
链式线性表的倒数第k项可以通过双指针法来实现。首先定义两个指针p和q,让p指向链表的头结点,q指向p的后k个节点。然后同时移动p和q指针,直到q指向链表的末尾。此时p指向的节点就是倒数第k个节点。
具体实现过程如下:
1. 定义两个指针p和q,让p指向链表的头结点,q指向p的后k个节点。
2. 同时移动p和q指针,直到q指向链表的末尾。
3. 返回p指向的节点。
代码实现如下:
```
ListNode* findKthToTail(ListNode* head, int k) {
if (head == nullptr || k <= ) {
return nullptr;
}
ListNode* p = head;
ListNode* q = head;
for (int i = ; i < k - 1; i++) {
if (q->next != nullptr) {
q = q->next;
} else {
return nullptr;
}
}
while (q->next != nullptr) {
p = p->next;
q = q->next;
}
return p;
}
```
其中,ListNode是链表节点的结构体,包含一个val成员表示节点的值,一个next成员表示指向下一个节点的指针。