C语言求链表的倒数第n个数

在C语言中，要求解链表的倒数第n个节点，通常可以通过两种方法实现：一种是两次遍历链表，另一种是使用双指针技巧。

1. 两次遍历链表：
这种方法首先遍历一次链表，计算出链表的总长度len，然后再遍历一次，这次遍历到第len-n个节点时停止，该节点即为倒数第n个节点。

2. 双指针技巧：
这种方法更为高效，只遍历一次链表。首先定义两个指针p和q，都指向链表的头节点。然后移动q指针，直到它移动了n个节点。之后，同时移动p和q两个指针，直到q指针指向链表的尾节点。此时，p指针指向的就是倒数第n个节点。

以下是使用双指针技巧的示例代码：

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

// 定义链表节点结构体
struct ListNode {
    int val;
    struct ListNode *next;
};

// 创建新节点的函数
struct ListNode* createNode(int val) {
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    newNode->val = val;
    newNode->next = NULL;
    return newNode;
}

// 求链表的倒数第n个节点的函数
struct ListNode* findNthToLast(struct ListNode* head, int n) {
    struct ListNode *p = head, *q = head;
    int count = 0;

    // 先让q指针前进n步
    while (count < n && q != NULL) {
        q = q->next;
        count++;
    }

    // 如果q指针已经到达链表末尾，说明n超过了链表长度
    if (q == NULL) {
        return NULL;
    }

    // 同时移动p和q，直到q到达链表末尾
    while (q->next != NULL) {
        p = p->next;
        q = q->next;
    }

    // 此时p指针指向倒数第n个节点
    return p;
}

int main() {
    // 构造一个简单的链表
    struct ListNode* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    head->next->next->next = createNode(4);
    head->next->next->next->next = createNode(5);

    // 假设我们要找到倒数第3个节点
    struct ListNode* nthToLast = findNthToLast(head, 3);

    if (nthToLast != NULL) {
        printf("倒数第n个节点的值为：%d\n", nthToLast->val);
    } else {
        printf("链表长度小于n\n");
    }

    // 释放链表内存
    struct ListNode* temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);
    }

    return 0;
}

这段代码展示了如何使用双指针技巧找到链表的倒数第n个节点。注意，在实际应用中，你可能需要先检查n的值是否有效（即n是否大于0，以及n是否小于或等于链表长度）。