C语言实现输出链表中倒数第k个节点

C语言实现输出链表中倒数第k个节点

题目描述

给定一个链表，要求实现一个函数输出该链表中倒数第k个节点。

解题思路

这道题可以通过两个指针来解决：一个指针先走k-1步，然后两个指针一起走，直到先走的指针到达链表的末尾。此时，后一个指针指向的就是链表中倒数第k个节点。

具体实现过程如下：

1. 定义两个指针 p1 和 p2，同时指向链表的头结点。
2. 让 p1 指针先走 k-1 步，即向后移动 k-1 个节点 。
3. 接着，让 p1 和 p2 两个指针同时向后移动，直到 p1 指向链表的尾节点为止。
4. 此时， p2 指向的节点就是链表中倒数第k个节点。

代码实现

下面是完整代码实现：

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

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

struct ListNode* getKthFromEnd(struct ListNode* head, int k){
    if (!head) return NULL;

    struct ListNode *p1 = head, *p2 = head;

    // 让p1指针先走k-1步
    for (int i = 0; i < k - 1; i++) {
        if (p1) p1 = p1->next;
        else return NULL;
    }

    // 同时移动p1和p2指针
    while (p1->next) {
        p1 = p1->next;
        p2 = p2->next;
    }

    return p2;
}

int main() {
    // 创建一个链表
    struct ListNode *head = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->val = 1;
    head->next = NULL;

    struct ListNode *p = head;

    for (int i = 2; i <= 5; i++) {
        struct ListNode *node = (struct ListNode*)malloc(sizeof(struct ListNode));
        node->val = i;
        node->next = NULL;
        p->next = node;
        p = p->next;
    }

    // 测试输出倒数第3个节点
    struct ListNode *res = getKthFromEnd(head, 3);

    if (res) printf("%d",res->val);

    return 0;
}

示例说明

我们将上述代码放入到C语言编译器（例如Dev-C++）中进行编译运行，得到输出结果为3。

再举一个实际一点的例子：比如我们有一条链表 1->2->3->4->5，想要输出倒数第2个节点，那么我们调用函数 getKthFromEnd(head, 2)，输出结果为4。