C语言面试题之返回倒数第 k 个节点

返回倒数第 k 个节点

实例要求

1、实现一种算法，找出单向链表中倒数第 k 个节点；
2、返回该节点的值；

示例：

输入： 1->2->3->4->5 和 k = 2
输出： 4
说明：

给定的 k 保证是有效的。

实例分析

1、定义快慢指针；
2、快指针先移动k步、链表长度小于k，返回特殊值；
3、快指针和慢指针同时移动，直到快指针到达链表末尾；
4、慢指针指向倒数第k个节点；

示例代码

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


int kthToLast(struct ListNode* head, int k){
    if (head == NULL || k <= 0) {
        return -1; // 返回一个特殊值表示无效输入
    }
    
    struct ListNode* fast = head;
    struct ListNode* slow = head;

    // 快指针先移动k步
    for (int i = 0; i < k; i++) {
        if (fast == NULL) {
            return -1; // 链表长度小于k，返回特殊值
        }
        fast = fast->next;
    }

    // 快指针和慢指针同时移动，直到快指针到达链表末尾
    while (fast != NULL) {
        fast = fast->next;
        slow = slow->next;
    }

    // 慢指针指向倒数第k个节点
    return slow->val;

}

代码解释

1、int kthToLast(struct ListNode* head, int k): 这个函数接收一个指向链表头部的指针 head 和一个整数 k，表示要找的倒数第 k 个节点。函数返回倒数第 k 个节点的值；
2、如果输入的链表头指针为空 head == NULL 或者 k 的值小于等于 0 k <= 0，则返回一个特殊值 -1，表示无效输入；
3、接着，定义两个指针 fast 和 slow，初始都指向链表的头部 head；
4、使用快慢指针的技巧，快指针 fast 先向前移动 k 步；
5、如果链表的长度小于 k，即快指针已经到达链表末尾时仍然为 NULL，则返回特殊值 -1，表示无效输入；
6、接着，快指针 fast 和慢指针 slow 同时向前移动，直到快指针 fast 到达链表末尾（即 fast == NULL）；
7、此时慢指针 slow 指向的节点就是倒数第 k 个节点，返回其值 slow->val。