7-1 求链式线性表的倒数第k项 (20 分)

链式线性表的倒数第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;
}

22-5 求链式线性表的倒数第K项

链式线性表的倒数第K项可以通过双指针法来实现。首先让一个指针从头开始遍历链表，直到走到第K个节点。然后再让另一个指针从头开始遍历链表，同时让第一个指针继续往后遍历，直到第一个指针走到链表末尾。此时第二个指针所指向的节点就是倒数第K个节点。

代码实现如下：

ListNode* findKthFromEnd(ListNode* head, int k) {
    ListNode* p1 = head;
    ListNode* p2 = head;
    for (int i = 0; i < k; i++) {
        p1 = p1->next;
    }
    while (p1 != nullptr) {
        p1 = p1->next;
        p2 = p2->next;
    }
    return p2;
}