大丰做网站,长春谁家做网站,关于医院网站建设的通知,建盏大师排名表2021返回倒数第 k 个节点
实例要求
1、实现一种算法#xff0c;找出单向链表中倒数第 k 个节点#xff1b;2、返回该节点的值#xff1b;
示例#xff1a;输入#xff1a; 1-2-3-4-5 和 k 2
输出#xff1a; 4
说明#xff1a;给定的 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初始都指向链表的头部 head4、使用快慢指针的技巧快指针 fast 先向前移动 k 步5、如果链表的长度小于 k即快指针已经到达链表末尾时仍然为 NULL则返回特殊值 -1表示无效输入6、接着快指针 fast 和慢指针 slow 同时向前移动直到快指针 fast 到达链表末尾即 fast NULL7、此时慢指针 slow 指向的节点就是倒数第 k 个节点返回其值 slow-val。
运行结果
