删除单链表的倒数第k个结点
删除 单链 结点 倒数第
2023-09-27 14:25:21 时间
策略
直接遍历总数为len,再次遍历第len-k+1个就是答案,但是这样遍历了O(N+k)个,可以在O在更短的时间内找到
图示
参考代码
#include <iostream> using namespace std; typedef struct ListNode { int value; ListNode* next; }ListNode; void createList(ListNode *&head) { head = new(ListNode); head->value = 1; head->next = NULL; ListNode *p2 = new(ListNode); p2->value = 2; p2->next = NULL; head->next = p2; ListNode *p3 = new(ListNode); p3->value = 3; p3->next = NULL; p2->next = p3; ListNode *p4 = new(ListNode); p4->value = 4; p4->next = NULL; p3->next = p4; } void deleteList(ListNode *p) { ListNode *next = NULL; while(p != NULL) { next = p->next; delete p; p = NULL; p = next; } } bool deleteKNode_2(ListNode *head, int k) { if(head == NULL || k <= 0) return false; ListNode *pre = head; for(int i = 0; i < k - 1; ++i) { if(pre == NULL) return false; pre = pre->next; } ListNode *cur = head; while(pre->next) { pre = pre->next; cur = cur->next; } cout << cur->value; cout << "succeed:" << endl; return true; } int main() { ListNode *head = NULL; createList(head); int k = 8; cout << "Result:" << deleteKNode_2(head, 2) << endl; deleteList(head); }
结果
三点注意
1. 指针为空
2. k<=0
3. k<len
相关文章
- 【算法】【链表模块】找到双向链表和单链表的倒数第k个元素删除并返回
- 删除单链表中的某一个值为num的节点
- k8s 删除命令空间namespace卡住解决方法
- C++ vector 和 map的删除
- 《Oracle SQL疑难解析》——1.9 从表中删除不需要的行
- Swift - 添加、修改、删除通讯录联系人
- rmdir -删除空目录
- win7 linux双系统删除linux
- Facebook Newswire删除法国尼斯恐袭视频
- 从Dart列表中删除重复项的2种方法
- 练习 2-9 在求对二的补码时,表达式x &= (x – 1)可以删除x中最右边值为1的一个二进制位。请解释这样做的道理。用这一方法重写bitcount函数,以加快其执行速度。