给定一个单向列表，请编写一个函数，删除列表的倒数第k个节点。要求：空间复杂度为O(1)，时间复杂度为O(n)，且只能遍历一次列表。

为了在一个单向链表中删除倒数第k个节点，并满足空间复杂度为O(1)和时间复杂度为O(n)，我们需要采用双指针的方法。假设有一个指向当前节点的指针p和一个距离指针q，初始时p都指向头节点，q指向头节点的前一个节点。

算法步骤如下：
1. 初始化两个指针p和q，分别指向链表的头节点和空（null），然后移动p k+1次，因为我们需要跳过前k个节点。
2. 当p到达链表尾部时，q就指向了倒数第k个节点的前一个节点。
3. 将q指向的节点的下一个节点赋给q指向的节点，这样就删除了倒数第k个节点，同时保持p和q的位置不变。
4. 返回原链表头部节点作为结果。

以下是伪代码形式：

def removeKthFromEnd(head, k):
    if head is None or k <= 0:
        return head

    p = head
    q = None
    for _ in range(k + 1):
        if p.next is None:
            break
        p = p.next

    if p is None:
        return head.next

    while p.next is not None:
        p = p.next
        q = q.next

    q.next = q.next.next
    return head

相关问题

用C++编写一个程序，给定一个单向列表，请编写一个函数，删除列表的倒数第k个节点。要求：空间复杂度为O(1)，时间复杂度为O(n)，且只能遍历一次列表。

在C++中，可以使用迭代的方式遍历链表，并同时维护两个指针，一个普通指针`prev`指向当前元素的前一个节点，另一个快指针`fast`每次移动两个节点。当`fast`到达链表尾部时，`prev`就会指向倒数第二个元素。然后我们可以简单地删除`prev`所指的节点，达到删除倒数第k个节点的效果。

下面是一个简单的示例代码：

#include <iostream>
using namespace std;

// 定义链表节点结构体
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

void removeKthFromEnd(ListNode* head, int k) {
    if (head == NULL || k <= 0) return; // 如果链表为空或k小于等于0，直接返回

    ListNode* slow = head;
    ListNode* fast = head;

    // 快慢指针先找到链表尾部
    for (int i = 0; fast && fast->next; ++i) {
        fast = fast->next->next;
    }

    // 如果k大于链表长度，则不需要删除任何节点
    if (fast == NULL) {
        return;
    }

    // 慢指针回溯到倒数第k个节点的前一个位置
    for (int i = 0; i < k - 1; ++i) {
        slow = slow->next;
    }

    // 删除倒数第k个节点
    if (slow != NULL) {
        slow->next = slow->next->next;
    }
}

// 测试函数
void printList(ListNode* head) {
    while (head) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    ListNode* list = new ListNode(1);
    list->next = new ListNode(2);
    list->next->next = new ListNode(3);
    list->next->next->next = new ListNode(4);
    list->next->next->next->next = new ListNode(5);

    cout << "Original List: ";
    printList(list);

    removeKthFromEnd(list, 2); // 删除倒数第二个节点

    cout << "After removing the second node from end: ";
    printList(list);

    return 0;
}

这个程序的空间复杂度为O(1)，因为它只使用了固定的额外空间存储两个指针；时间复杂度为O(n)，因为需要遍历链表两次，一次用于找到倒数第k个节点的位置，一次用于删除节点。

2. 算法设计题，以下每道题请给出C++代码，并给出必要的注释。 给定一个单向列表，请编写一个函数，删除列表的倒数第个节点。要求：空间复杂度为O(1)，时间复杂度为O(n)，且只能遍历一次列表。

为了实现这个功能，我们可以创建一个指向当前节点的指针 `prev` 和一个指向最后一个访问过的节点的指针 `last`。在遍历过程中，当找到最后一个节点时，将其前一个节点设为 `null` 即可删除倒数第1个节点。

以下是对应的 C++ 代码实现：

#include <iostream>
using namespace std;

// 定义链表节点结构体
struct ListNode {
    int val; // 节点值
    ListNode *next; // 指向下个节点
    ListNode(int x) : val(x), next(NULL) {} // 构造函数
};

// 删除链表的倒数第一个节点
ListNode* deleteLast(ListNode* head) {
    if (head == nullptr || head->next == nullptr) { // 如果链表为空或只有一个元素
        return nullptr;
    }
    
    ListNode *prev = head, *current = head->next; // 初始化 prev 和 current
    while (current->next != nullptr) { // 遍历链表，直到找到最后一个节点
        prev = current;
        current = current->next;
    }

    // 当找到最后一个节点时，将它的前一个节点设置为 null
    prev->next = NULL;

    return head; // 返回头节点，现在链表已更新
}

int main() {
    // 创建示例链表
    ListNode *list = new ListNode(1);
    list->next = new ListNode(2);
    list->next->next = new ListNode(3);

    // 打印原链表
    ListNode *temp = list;
    while (temp != nullptr) {
        cout << temp->val << " ";
        temp = temp->next;
    }
    cout << endl;

    // 删除倒数第一个节点后打印链表
    list = deleteLast(list);
    temp = list;
    while (temp != nullptr) {
        cout << temp->val << " ";
        temp = temp->next;
    }
    cout << endl;

    return 0;
}