摘要：文章目录链表的中间结点链表中倒数第个结点链表的中间结点相信对于学习链表的初学者来说，首次看到这个题目时，首先想到的应该是通过对整个链表进行一遍遍历求出链表节点的个数，然后再通过循环来找到中间节点实不相瞒我第一次也是这样想的。
相信对于学习链表的初学者来说，首次看到这个题目时，首先想到的应该是通过对整个链表进行一遍遍历求出链表节点的个数，然后再通过循环来找到中间节点(实不相瞒我第一次也是这样想的)。但是通过两次循环，不免增加了代码量和时间复杂度。那么，接下来就介绍一下最优的解题思路。
最优思路
定义两个指针，其中一个指针为慢指针，另一个指针为快指针，对本题而言，慢指针每次走一步(向前移动一个节点)，快指针每次走两步(向前移动两个节点)，当快指针走到链表末尾时，此时的慢指针就正好移动到链表的中间节点。图解如下：
代码如下：
struct ListNode* middleNode(struct ListNode* head){ struct ListNode*n1=head,*n2=head; //定义两个指针，分别为快慢指针 while(n2 && n2->next) //当快指针指向最后一个节点或者指向NULL时结束 { n1=n1->next; //每次向前走一步 n2=n2->next->next; //每次向前走两步 } return n1;}
根据上一题的思路，我们可以借鉴双指针来解决这道题，即先让一个指针先向前走动 K 步，再让另一个指针从头节点开始走，当前一个指针走到链表尾节点的 next 域时（即指向NULL时），此时的后一个指针就指向的链表中的倒数第K个节点。图解如下：
代码如下：
class Solution {public: ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) { ListNode* slow=pListHead; ListNode*fast=pListHead; while(k--) //使fast指针向向前走动K个节点 { if(fast==NULL) return NULL; //处理特殊情况，当链表为空链表时，返回NULL(下同) fast=fast->next; } while(fast) { fast=fast->next; slow=slow->next; } if(slow==NULL) { return NULL; //处理特殊情况，同上 } return slow; }};通过以上两题我们可以知道，在通常需要求链表中某个位置的节点时，除了使用遍历的方法外，还应当想到比较优的双指针(快慢指针)的方法，这样的时间复杂度和代码量都得到了很好的优化。
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/123307.html
摘要：说明不允许修改给定的链表。注意，函数返回结果后，链表必须保持其原始结构。示例输入输出解释相交节点的值为注意，如果两个链表相交则不能为。将这两数相加会返回一个新的链表。 ...
摘要：同时让当前结点的指针指向，从而实现从链表尾部开始的局部反转当递归函数全部出栈后，链表反转完成。这个链表的倒数第个节点是值为的节点。新链表是通过拼接给定的两个链表的所有节点组成的。 目录 1.反转链表 K个一组翻转链表 链表的中间节点： 链表倒数第k个节点： 删除链表倒数第k个节...
摘要：同时保有当前链表的尾部的指针以及头部的节点指针。链表可能只有部分成环这意味着。头部的引用尾部的引用始终指向尾部忽略虚假的头部链表相加原题地址。生成虚假的头部后两个链表两两相加注意进位以及保留位即可。链表是没有发生改变的。 showImg(https://segmentfault.com/img/remote/1460000018562166?w=1069&h=600); 前言 本文基于...
摘要：构建双指针距离前指针先向前走步结束后，双指针和间相距步。它们起始都位于链表的头部。随后，指针每次向后移动一个位置，而指针向后移动两个位置。 【Java数据结构】...
摘要：前言本章将分享十一道来自牛客网中的经典链表算法题来介绍数据结构中链表在算法题中的应用。注意，函数返回结果后，链表必须保持其原始结构。 前言：本章将分享十一道来自Le...
阅读 704·2023-04-25 19:17
阅读 2740·2021-11-15 11:38
阅读 3611·2021-09-29 09:34
阅读 1834·2021-09-10 11:26
阅读 1688·2019-08-30 15:54
阅读 3293·2019-08-30 15:53
阅读 2529·2019-08-30 11:20
阅读 3254·2019-08-29 15:12
