链表返回倒数第k个数据，怎么改

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


int kthToLast(struct ListNode* head, int k){
struct ListNode* pre=NULL;
struct ListNode* cur=head;
struct ListNode* h=head;
while(cur!=NULL){
struct ListNode* next=cur->next;
cur->next=pre;
pre=cur;
cur=next;
}

int* arr=(int*)calloc(10000,sizeof(int));

int i=0;

while(h->next!=NULL){
arr[i]=h->val;
h=h->next;
i++;

}

return arr[k];

}

可以不使用数组来实现链表返回倒数第k个数据，可以使用双指针法。定义两个指针p和q，p先向前移动k个节点，然后p和q同时向前移动，当p到达链表尾部时，q所指向的节点即为倒数第k个节点。修改后的代码如下：

int kthToLast(struct ListNode* head, int k){
    struct ListNode* p = head;
    struct ListNode* q = head;
    for(int i=0; i<k; i++){
        p = p->next;
    }
    while(p!=NULL){
        p = p->next;
        q = q->next;
    }
    return q->val;
}

需要注意的是，要先判断链表长度是否小于k，否则会出现超出链表长度的情况，可以在第一次遍历时先计算链表长度，如果长度小于k，直接返回NULL或者特定的错误码。

【以下回答由 GPT 生成】

我可以给出一个使用双指针法来解决该问题的方案。

双指针法的思路是使用两个指针p和q，初始时p和q都指向链表的头结点。然后，让指针q先向前移动k个位置，然后指针p和q同时向前移动，直到q指向链表的末尾。此时，指针p就指向了倒数第k个节点。

具体的实现步骤如下：

1. 判断输入的k是否合法。如果k小于等于0，或者链表为空，或者链表的长度小于k，直接返回-1表示错误。

2. 定义两个指针p和q，初始时它们都指向链表的头结点。

3. 让指针q先向前移动k个位置。如果链表的长度小于k，移动到末尾时q将为NULL。

4. 如果q为NULL，表示链表的长度小于k，返回-1表示错误。

5. 否则，指针p和q同时向前移动。每次移动一个位置，直到q指向链表的末尾。这样，指针p就指向了倒数第k个节点。

6. 返回指针p所指向的节点的值。

以下是改进后的代码实现：

int kthToLast(struct ListNode* head, int k) {
    if (k <= 0 || head == NULL) {
        return -1; // 错误输入
    }

    struct ListNode* p = head;
    struct ListNode* q = head;

    for (int i = 0; i < k; i++) {
        if (q == NULL) {
            return -1; // 链表长度小于k
        }
        q = q->next;
    }

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

    return p->val;
}

这样实现的时间复杂度为O(n)，空间复杂度为O(1)。由于只用了常数级别的额外空间，因此更高效。

【相关推荐】

• 这有个类似的问题, 你可以参考下: https://ask.csdn.net/questions/7599480
• 你也可以参考下这篇文章：链表中倒数第K个节点
• 您还可以看一下 程媛媛老师的期货量化交易麦语言编程初级课程中的 K线形态描述编程小节, 巩固相关知识点
  
• 除此之外, 这篇博客: 每日十道算法中的  2、返回倒数第 k 个节点 部分也许能够解决你的问题。