C++实现单链表删除倒数第k个节点的方法
本文实例讲述了C++实现单链表删除倒数第k个节点的方法。分享给大家供大家参考，具体如下：
题目：
删除单链表中倒数第k个节点
解题思路及算法代码：
标尺法，定义两个指针指向链表头结点，先让一个走k步，然后两个指针同时开始走，当先走的指针走到末尾时，后走的指针指向的结点就是需要删除的结点。
单链表结构定义：
typedef struct Node
{
int data;
struct Node* next;
}node, *pLinkedList;
删除倒数第K结点操作代码：
//head表示头结点
Node* removeLastKthNode(pLinkedList head, int k)
{
if (NULL == head->next || k < 1)
return head;
pLinkedList cur = head; //1号指针
pLinkedList ret = head; //2号指针，指向待删除节点
pLinkedList pre = NULL; //pdel待删除节点的前一个节点
/*
head 1 2 3 4 5
cur
ret
*/
while (k > 0 && cur != NULL)
{
k--;
cur = cur->next;
}
//当链表走到终点时，k仍然大于0，可知k值大于链表长度
if (k > 0 && cur == NULL)
{
cout << "k值大于链表长度" << endl;
return head;
}
//k == 0时，1号指针和2号指针同时走,ret即为待删除的节点
if (k == 0)
{
while (cur != NULL)
{
pre = ret;
cur = cur->next;
ret = ret->next;
}
/*k = 2时
head 1 2 3 4 5 NULL
pre ret cur
即要求删除ret节点
*/
pre->next = ret->next;
free(ret);
ret = NULL;
return head;
}
}
希望本文所述对大家C++程序设计有所帮助。
-
本文向大家介绍C语言实现输出链表中倒数第k个节点，包括了C语言实现输出链表中倒数第k个节点的使用技巧和注意事项，需要的朋友参考一下 本文实例展示了C++实现输出链表中倒数第k个节点的方法，分享给大家供大家参考之用。 运行本文所述实例可实现输入一个单向链表，输出该链表中倒数第k个节点。 具体实现方法如下： 测试用例如下： 1. NULL Link head = NULL; 2. normal
-
本文向大家介绍Java输出链表倒数第k个节点，包括了Java输出链表倒数第k个节点的使用技巧和注意事项，需要的朋友参考一下 问题描述 输入一个链表，输出该链表中倒数第k个结点。(尾结点是倒数第一个) 结点定义如下： 思路1： 先遍历链表，计算其长度length; 然后计算出倒数第k个结点就是正数第length - k + 1. 最后再遍历链表，找到所求结点 时间复杂度O(2n),需要遍历两次链表
-
一、题目 输入一个链表，输出该链表中倒数第k 个结点。为了符合大多数人的习惯，本题从1 开始计数，即链表的尾结点是倒数第1 个结点．例如一个链表有6 个结点，从头结点开始它们的值依次是1 、2、3、4、5 、6。这个个链表的倒数第3 个结点是值为4 的结点。 二、解题思路 为了实现只遍历链表一次就能找到倒数第k 个结点，我们可以定义两个指针。第一个指针从链表的头指针开始遍历向前走k-1步，第二个指
-
本文向大家介绍PHP获取链表中倒数第K个节点的方法，包括了PHP获取链表中倒数第K个节点的方法的使用技巧和注意事项，需要的朋友参考一下 本文实例讲述了PHP获取链表中倒数第K个节点的方法。分享给大家供大家参考，具体如下： 问题 输入一个链表，输出该链表中倒数第k个结点。 解决思路 注意这个题目是返回节点，而不是返回值。返回值的话可以用栈来存储。返回节点则不能这样做。 设置两个指针，先让第一个指针移
-
NowCoder 解题思路 设链表的长度为 N。设置两个指针 P1 和 P2，先让 P1 移动 K 个节点，则还有 N - K 个节点可以移动。此时让 P1 和 P2 同时移动，可以知道当 P1 移动到链表结尾时，P2 移动到第 N - K 个节点处，该位置就是倒数第 K 个节点。 // java public ListNode FindKthToTail(ListNode head, int k
-
本文向大家介绍C++删除链表中间节点的方法，包括了C++删除链表中间节点的方法的使用技巧和注意事项，需要的朋友参考一下 本文实例讲述了C++删除链表中间节点的方法。分享给大家供大家参考，具体如下： 题目： 给定链表头结点head，实现删除链表的中间节点函数。 解题思路及代码： 快慢指针，快指针走两步，慢指针一步。 当快指针走到终点时，慢指针正好是链表中间节点，删除此节点即可。 链表结构定义： 算法