单链表有很多常用操作，有些操作比较有技巧。本篇就说说这些不容易想到的操作。单链表倒数第k个节点单链表的前向第k个节点很容易获得。直接用for循环遍历链表就可以得到。但是反方向的第k个节点，即倒数第k个节点呢？你可能很快就想到，反向的第k个节点相当于正向的n-k个节点，其中n是链表的长度。对于单链表，需要遍历链表计算出n的值，然后再遍历n-k个节点，最终得到链表倒数第k个节点。上面整个过程一共遍历了n+n-k个节点。只遍历n个节点能不能得到倒数第n个节点？答案是肯定的。这种解决方法叫做双指针法，比较巧妙。如果没有接触过的话，想起来也不容易。下面就来详细介绍一下。如果k=2，现在让指针p1指向头结点，然后移动k步，结果如下图所示：此时，如果p1移动n-k步，就会到达空结点在链接列表的末尾。然后用一个指针p2指向头节点。指针p1和p2指向如下图所示：最后，指针p1和p2同时向前移动，直到p1到达链表尾部的空节点。此时，两个指针的指向如下图所示：当p1到达空节点时，p2走n-k步，即倒数第k个节点。这样，利用p1和p2这两个指针，只需要遍历一次链表就可以得到倒数第k个结点，也就是p2指向的结点。在整个过程中，使用了两个指针，因此这种技术被称为双指针法。许多与链表相关的算法问题都可以用这种技术来解决。了解了这个套路之后，以后解决类似的问题就很容易了。好了，流程到此结束，下面是完整的代码供大家参考：//单向链表节点结构structListNode{intval;列表节点*下一个；ListNode(intx):val(x),next(nullptr){}ListNode(intx,ListNode*pnext):val(x),next(pnext){}};//返回从底部开始的第k个节点单链表ListNode*findFromEnd(ListNode*head,intk){if(nullptr==head||k<=0)returnnullptr;列表节点*p1=头；//p1指针先移动k步intstep=0;while(stepnext;++步骤；}//p1移动的步数小于k，说明链表长度小于k//因此链表没有从底部开始的第k个节点if(stepnext;p1=p1->下一个；}returnp2;}单链表中点想要得到单链表的中点，首先想到的是先得到链表的长度n，然后从链表的头部开始向前移动链。每一步，计数都会增加1，直到计数达到n/2，这是链表长度的一半。此时的节点是链表的中间。点击。但是这种方法需要先遍历整个链表，然后从链表的头部遍历到链表的中间节点。整个过程一共遍历n+n/2个节点。这里有一个方法，只需要遍历n个节点，就可以得到链表的中间节点。我们让指针p1和p2都指向头结点，两个指针同时向前移动，p1每次向前走两步，p2每次向前走一步，这样当p1到达尾节点时在链表中，p2刚好到达链表的中间节点。在这个过程中，p1指针一次移动两步，称为快指针，p2指针一次移动一步，称为慢指针，所以这一招称为快慢指针。根据以上思路，我们就可以编写算法的实现代码了。//单链表节点结构structListNode{intval;列表节点*下一个；ListNode(intx):val(x),next(nullptr){}ListNode(intx,ListNode*pnext):val(x),next(pnext){}};//返回单链的中间节点listListNode*middleNode(ListNode*head){if(nullptr==head)returnnullptr;//快指针和慢指针最初都指向headListNode*pslow=head;ListNode*pfast=head;while(nullptr!=pfast&&nullptr!=pfast->next){//快指针每走两步，慢指针走一步//当快指针的下一个节点为空时//表示快指针到达结束节点，此时退出循环pfast=pfast->next->next;pslow=pslow->下一步；}返回pslow；，上述解决方案返回最后一个节点。例如：单链表1->2->3->4->5->6，长度为6，其中间节点为3和4，那么，上述解法得到的中间节点为4，而不是3.链表是否包含环如下图所示。图中是一个链表，长度为5，最后一个节点指向第三个节点，形成一个环。给定单向链表的头节点，判断链表是否包含环。如何判断单向链表是否存在环？我们可以借用单链表中点的思想。快慢指针与起始节点同时向前移动。在没有环的单向链表中，它们依次到达尾节点，但是对于有环的链表，快慢指针总是在环的末端移动，永不停止。由于两个指针一个一个慢，而快指针每次都比慢指针多走一步，所以总有一天快指针会追上慢指针，此时它们都指向同一个节点。判断单链是否有表环的方法是：一开始，快慢指针分别指向头节点，同时向前移动。快指针每次走两步，慢指针每次走一步。当快指针和慢指针相等时，说明链表有环。如果快指针的下一个结点是空结点，说明链表没有环路。根据以上思路，就可以编写实现代码了。//返回单链表是否有环boolhasCycle(ListNode*head){if(nullptr==head)returnfalse;//快指针和慢指针最初都指向headListNode*pslow=head;ListNode*pfast=head;while(nullptr!=pfast&&nullptr!=pfast->next){//快指针每次走两步，慢指针每次走一步//当快指针的下一个节点为null//表示fast指针已经到达尾节点pfast=pfast->next->next;pslow=pslow->下一步；如果（pfast==pslow）{返回真；}}returnfalse;}链表环的起始节点再深入一点，既然解决了链表有环的问题，能知道环的起始节点吗？例如：下图中的链表，环的起始节点为3。解决方案还是使用快慢指针，快指针一次走两步，慢指针走一步一次。下图是一个简单的循环链表图，其中A是链表的头节点，B是环的起始节点，C是环中快指针和慢指针相交的节点（如至于为什么快指针和慢指针一定要在环的中间相交，上一节已经解释过了，这里不再赘述）。A到B的距离为S1。B到C的距离为S2。C到B的距离是S3。假设当快指针和慢指针在C点相遇时，快指针已经绕环走了n圈，相遇时各自走过的距离为：快指针：S1+n*(S2+S3)+S2。慢指针：S1+S2。由于快指针行进的距离是慢指针行进的距离的两倍，则：S1+n*(S2+S3)=2*(S1+S2)将上式化简可得：S1=(n-1)*(S2+S3)+S3S2+S3正好是圆环的长度，所以上面的结果可以理解为，A到B的距离等于从交汇点C开始，绕圆环走n-1圈（此时会回到C点），然后走S3到达B点，也就是环路的起点。因此，当快慢指针相遇时，用一个附加指针指向链表的头节点，然后附加指针和慢指针同时移动，最终会在起始节点相遇戒指的。理解了上面的推理过程后，可以根据链表是否存在环路，对实现代码稍作修改。具体代码如下：//返回单链表循环的起始节点ListNode*entrynodeInLoop(ListNode*head){if(nullptr==head||nullptr==head->next)returnnullptr;列表节点*pslow=head;//慢指针ListNode*pfast=head;//快指针ListNode*ppoint=nullptr;//指向快指针和慢指针相遇的节点while(nullptr!=pfast&&nullptr!=pfast->next){pslow=pslow->next;pfast=pfast->下一步->下一步；如果（pslow==pfast）{ppoint=pslow;休息;}}//遇到节点为null，说明没有循环if(nullptr==ppoint)returnnullptr;pslow=头；//慢指针指向头节点while(pslow!=ppoint){pslow=ppoint->next;ppoint=ppoint->下一个；}returnppoint;}其实对于链表是否有环以及链表环的起始节点还有更直观的解决方法。添加一个额外的记录节点指针集合，然后从头节点开始向前遍历。每次传递一个节点时，检查该节点是否已存在于集合中。如果不存在，则将节点指针添加到集合中。如果存在，则说明该节点是环的入口节点。这种方法很容易理解，但是它的空间复杂度是O(N)，时间复杂度和快慢指针一样。这里也给出了实现代码，供参考。//返回链表循环的起始节点ListNode*entrynodeInLoop(ListNode*head){if(nullptr==head)returnnullptr;//链表节点集合unordered_setsetnode;列表节点*p=头；while(nullptr!=p){autoiter=setnode.find(p);if(iter!=setnode.end()){//在集合中找到相同的节点//这个节点是环的入口returnp;}//节点不在集合中，则加入集合setnode.insert(p);//移动到下一个节点p=p->next;}//没有环，returnnullptrreturnnullptr;}两个链表是否交给你两个链表的头节点，如果两个链表相交，则返回相交的节点，如果不相交，则返回null。比如下图中，两个链表相交的节点是3。乍一看这道题，最容易想到的方法就是分别遍历两个链表，用一个集合记录节点在遍历过程中。如果有相交节点，这个节点肯定会被访问多次。第二次访问该节点时，该节点已经存在于集合中，如果不存在交集，则集合中不存在两个相同的节点。但是使用集合暂存遍历节点的方法，空间复杂度为O(N)，在O(1)的空间复杂度内如何解决呢？解决方法是使用两个指针p1和p2，一开始p1指向第一个链表的头节点，p2指向第二个链表的头节点，然后同时开始遍历链表，之后p1遍历链表，指向第二个链表的头节点，p2遍历链表后，指向第一个链表的头节点。其实相当于把两个链表连在一起。详见下图：图中绿色节点为当前链表的节点，蓝色节点为其他链表的节点，红色为遍历过程中遇到的节点，即两个链表相交的节点，当两个链表不相交时，p1和p2最后都指向空节点，这也是我们想要的结果，大家可以自己模拟这个过程。所以，这道题的关键是想办法让p1和p2同时到达两个链表相交的节点。按照上面的方法，实现代码可以这样写：//单向链表节点结构structListNode{intval;列表节点*下一个；ListNode(intx):val(x),next(nullptr){}ListNode(intx,ListNode*pnext):val(x),next(pnext){}};//返回两个链表相交的节点ListNode*getIntersectionNode(ListNode*headA,ListNode*headB){if(nullptr==headA||nullptr==headB)returnnullptr;列表节点*pa=headA;列表节点*pb=headB;while(pa!=pb){pa=(nullptr!=pa)?pa->下一个：headB；pb=(nullptr!=pb)?pb->下一个：headA；}returnpa;}小结本文讲解链表相关的一系列操作。能掌握并熟练运用这些套路的人
