查找链表中倒数第k个位置上的结点 C语言实现

要实现查找链表中倒数第k个位置上的节点，可以使用双指针法。

首先，定义两个指针p和q，初始时都指向链表的头节点。然后，将指针p向前移动k个位置，使得p指向链表中的第k个节点。

接下来，同时移动指针p和q，直到p指向链表的末尾节点。此时，q所指向的节点即为链表中倒数第k个位置上的节点。

下面是一个示例的C语言代码实现：

#include <stdio.h>
#include <stdlib.h>

// 定义链表节点结构体
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 查找链表中倒数第k个位置上的节点
Node* findKthFromEnd(Node* head, int k) {
    if (head == NULL || k <= 0) {
        return NULL;
    }
    
    Node* p = head;
    Node* q = head;
    
    // 将指针p向前移动k个位置
    for (int i = 0; i < k; i++) {
        if (p == NULL) {
            return NULL;  // 链表长度小于k
        }
        p = p->next;
    }
    
    // 同时移动指针p和q
    while (p != NULL) {
        p = p->next;
        q = q->next;
    }
    
    return q;
}

// 创建链表
Node* createLinkedList(int arr[], int n) {
    if (n <= 0) {
        return NULL;
    }
    
    Node* head = (Node*)malloc(sizeof(Node));
    head->data = arr[0];
    head->next = NULL;
    
    Node* tail = head;
    for (int i = 1; i < n; i++) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = arr[i];
        newNode->next = NULL;
        
        tail->next = newNode;
        tail = newNode;
    }
    
    return head;
}

// 打印链表
void printLinkedList(Node* head) {
    Node* p = head;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

// 销毁链表
void destroyLinkedList(Node* head) {
    Node* p = head;
    while (p != NULL) {
        Node* temp = p->next;
        free(p);
        p = temp;
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    Node* head = createLinkedList(arr, n);
    
    printf("原链表：");
    printLinkedList(head);
    
    int k = 2;
    Node* kthNode = findKthFromEnd(head, k);
    
    if (kthNode != NULL) {
        printf("倒数第%d个位置上的节点的值为：%d\n", k, kthNode->data);
    } else {
        printf("链表长度小于%d\n", k);
    }
    
    destroyLinkedList(head);
    
    return 0;
}

上述代码中，首先创建了一个链表，然后调用findKthFromEnd函数查找倒数第k个位置上的节点，并打印出该节点的值。

注意：在实际使用中，需要对输入的数据进行合法性检查，以确保程序的健壮性。