查找单向链表倒数第k个位置上的结点。 在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k(k > 0)个位置的节点。 /** * Definition for singly-linked list. * struct Node { * int val; * Node * next; * Node(int x) : val(x), next(NULL) {} * }; */

可以采用双指针的方法来查找单向链表中倒数第k个位置的节点。

首先定义两个指针p和q，将它们都指向链表的头节点。然后让指针q先向后移动k个位置，接着同时移动指针p和q，直到指针q到达链表的末尾位置。此时指针p所指向的节点即为链表倒数第k个位置的节点。

具体实现如下：

Node* findKthToTail(Node* head, int k) {
    if (head == nullptr || k <= 0) {
        // 链表为空或k无效，返回nullptr
        return nullptr;
    }

    Node* p = head;
    Node* q = head;
    for (int i = 0; i < k; i++) {
        if (q == nullptr) {
            // 链表长度小于k，返回nullptr
            return nullptr;
        }
        q = q->next;
    }

    while (q != nullptr) {
        p = p->next;
        q = q->next;
    }

    return p;
}

时间复杂度为O(N)，空间复杂度为O(1)。

相关问题

算法输入一个单向链表，输出该链表中倒数第k个结点，链表的最后一个结点是倒数第1个节点。

可以使用双指针法来解决该问题。首先让第一个指针从链表头开始向前移动k-1个节点，然后同时移动第一个和第二个指针，直到第一个指针到达链表尾部，此时第二个指针所指的节点即为倒数第k个节点。

代码实现如下：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def findKthToTail(head, k):
    if not head or k <= 0:
        return None
    p1, p2 = head, head
    for i in range(k-1):
        if not p1.next:
            return None
        p1 = p1.next
    while p1.next:
        p1 = p1.next
        p2 = p2.next
    return p2

# 测试代码
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node5 = ListNode(5)

node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

print(findKthToTail(node1, 2).val)  # 输出4

用C＋＋算法实现输入一个单向链表,输出该链表中倒数第k个结点,链表的最后一个结点是倒数第一个结点，并输出测试用例

在C++中，可以使用双指针法（快慢指针）来解决这个问题。我们创建两个指针，初始时都指向头节点。然后让快指针每次向前移动k步，慢指针每次只前进一步。当快指针到达链表尾部时，慢指针的位置就是倒数第k个节点。

以下是简单的代码实现：

#include <iostream>

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* findKthToTail(ListNode* head, int k) {
    if (!head || !k) return nullptr; // 链表为空或k为0的情况

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

    for (int i = 0; i < k - 1; ++i) {
        if (fast) fast = fast->next;
    }

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    return slow;
}

// 测试用例
void test_case() {
    // 创建链表示例: 1 -> 2 -> 3 -> 4 -> 5
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);

    int k = 3; // 查找倒数第三个节点
    ListNode* result = findKthToTail(head, k);
    if (result != nullptr) {
        std::cout << "倒数第" << k << "个节点的值是: " << result->val << std::endl;
    } else {
        std::cout << "链表太短，无法找到倒数第" << k << "个节点" << std::endl;
    }
    delete result;
}

int main() {
    test_case();
    return 0;
}

在这个例子中，`findKthToTail`函数会返回倒数第k个节点，如果k大于链表长度，则返回nullptr。你可以修改`test_case`中的链表和k值来测试其他情况。