大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
题目描述:单链表查找倒数第k个节点
创新互联建站主营盐边网站建设的网络公司,主营网站建设方案,重庆APP开发,盐边h5成都微信小程序搭建,盐边网站营销推广欢迎盐边等地区企业咨询分析:单链表是一个单向的链式结构,所以不可能从链表尾部向前找第k个结点,因此只能想办法从链表的头部开始找。
假设一个给定一个链表,长度为 6,现在查找倒数第 2 个结点:
给定两个指针, fast 和 slow 开始都让他们指向头结点
首先,让 fast 指针先走到正数第 k 个结点,也就是走 k-1 步,这里 k=2,所以先让 fast 走1步
这时让 slow 指针跟着 fast 指针一块走,直到 fast 指针走到最后一个节点(注意:这里是最后一个节点,而不是空节点),此时 slow 指针所指向的节点就是我们要找的倒数第 k 个结点了
当然,这里只是大致的思想,具体的很多细节问题(比如: k值大于链表的长度,k = 0 的情况等等),需要自己处理。
主要代码如下:
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) { if(pListHead == NULL || k == 0) //一些异常情况 { return NULL; } ListNode* fast = pListHead; ListNode* slow = pListHead; while(fast && --k) //这里一定要先自减,因为两个指针开始都指向头结点 { fast = fast->next; } if(fast == NULL) //即没找到的情况 { return NULL; } if(k == 0) { while(fast->next != NULL) { fast = fast->next; slow = slow ->next; } } return slow; }
创新互联www.cdcxhl.cn,专业提供香港、美国云服务器,动态BGP最优骨干路由自动选择,持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证, 机房独有T级流量清洗系统配攻击溯源,准确进行流量调度,确保服务器高可用性。佳节活动现已开启,新人活动云服务器买多久送多久。