双指针还有这妙用？学到了！

我就是我 2022-12-11 03:17 175阅读 0赞

点击上方“**五分钟学算法**”，选择“星标”公众号

重磅干货，第一时间送达![format_png][]

![format_png 1][]

在面试中，链表相关的问题出现频率非常高，而很多问题都有一些类似的技巧，今天分享快慢指针的技巧。

## 返回链表的中间节点 ##

题目：

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
    如果有两个中间结点，则返回第二个中间结点。

分析：  
这题最容易想到的做法就是先获取到链表的长度L，如果链表长度是偶数，那么中间节点就是L/2 + 1，如果是奇数，则是L/2。同样的，这种方法需要遍历两次链表。那么使用快慢指针怎么做呢？

*  快慢指针同时指向头节点，快指针走两步，慢指针走一步
 *  如果长度为偶数，那么快指针为NULL的时候停止，长度为奇数，fast->next为NULL的时候停止
 *  慢指针指向的位置就是中间节点了

按照这种思路，实现代码如下：

//来源：公众号【编程珠玑】
    //作者：守望先生
    LinkNode *findMidNode(LinkNode *head)
    {
        LinkNode *fast = head;
        LinkNode *slow = head;
    
        while (NULL != fast && NULL != fast->next )
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }

## 链表的中间节点 ##

题目：

题目：
    
    输入一个单向链表，输出该链表中倒数第k个结点。为符合计数习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
    
    例子
    
    如：一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

分析：  
由于单向链表并不能从末尾开始数，因此没有办法直接得出倒数第k个节点。但是这也不难，我们可以计算出链表的长度l，然后再从头数到l-k，即可得到倒数第k个节点。

但是这种方法需要遍历两次！有没有遍历一次的方法呢？

思路：  
定义两个指针，指针移动一个快，一个慢  
1.快慢指针同时指向头结点  
2.首先快指针移动k-1步，先走到第k个节点  
3.快慢指针同时移动，直到快指针指向末尾，这时，快慢指针都走了l-k，  
4.慢指针指向的节点即为我们需要寻找的节点

举个例子，有链表值依次为1,2,3,4,5,6，找到倒数第三个节点：

先让快指针移动3-1步。

然后快慢同时移动,直到fast到达末尾：

看到了吗，这时候slow就指向了倒数第三个节点。

我们的参考代码实现如下：

//来源：公众号【编程珠玑】
    //作者：守望先生
    //https://www.yanbinghu.com
    LinkNode *FindKthToTail(LinkNode *head,unsigned int k)
    {
        if(NULL == head || 0 == k)
            return head;
        LinkNode *pFast = head;
        LinkNode *pSlow = head;
        unsigned int i = 0;
        //快指针先移动
        while(i < k -1)
        {
            if(NULL != pFast)
            {
                pFast = pFast->next;
            }
            //k大于链表的长度
            else
            {
                return NULL;
            }
            i++;
        }
        //快慢指针一起移动
        while(NULL != pFast->next)
        {
            pSlow = pSlow->next;
            pFast = pFast->next;
        }
        return pSlow;
    }

## 判断链表是否有环 ##

题目：如何判断一个单链表是否有环？若有环，如何找出环的入口节点。

按照快慢指针的思路，使用两个指针，一个指针每次走一步，另一个每次走两步，如果链表有环，那么它们终将相遇，而如果没有环，快的指针最后会指向NULL。  
按照这种思路，我们的参考代码如下：

//来源：公众号【编程珠玑】
    //作者：守望先生
    //0:无环，1：有环
    int hasLoop(LinkNode *head)
    {
    
        if(NULL == head)
            return 0;
        LinkNode *slow = head;
        LinkNode *fast = head->next;
        //当快指针到末尾时，无环，结束
        while (NULL != fast  && NULL != slow) 
        {
            //快慢相遇，有环
            if (fast == slow)
                return 1;
            slow = slow->next; // 慢指针每次走一步
    
            fast = fast->next;
            if (fast != NULL)
                fast = fast->next;
        }
        return 0;
    }

## 完整可运行参考代码 ##

**阅读原文**可查看完整可运行示例代码。

//来源：公众号【编程珠玑】
    //作者：守望先生
    #include <stdio.h>
    #include <stdlib.h>
    typedef int NodeVal;
    typedef struct LinkNode_t
    {
        NodeVal val;
        struct LinkNode_t *next;
    }LinkNode;
    
    LinkNode *createLinkNode(NodeVal *arr,size_t n){
        LinkNode *head = NULL, *node = NULL, *end = NULL;//定义头节点，普通节点，尾部节点；
    
        for (size_t i = 0; i < n; i++) {
            node = (LinkNode*)malloc(sizeof(LinkNode));
            //创建头节点
            if(NULL == head)
            {
                head = node;
                head->val = arr[i];
                end = head;
            }
            else
            {
                node->val = arr[i];
                end->next = node;
                end = node;
            }
    
        }
        end->next = NULL;//结束创建
        return head;
    
    }
    //释放资源
    void destoryLinkNode(LinkNode *head)
    {
        LinkNode *pn = NULL;
    
        while (NULL != head)
        {
            if(NULL == head->next)
            {
                free(head);
                head = NULL;
            }
            else
            {
                pn = head->next->next;
                free(head->next);
                head->next = pn;
            }
        }
    }
    LinkNode *FindKthToTail(LinkNode *head,unsigned int k)
    {
        if(NULL == head || 0 == k)
            return head;
        LinkNode *pFast = head;
        LinkNode *pSlow = head;
        unsigned int i = 0;
        //快指针先移动
        while(i < k -1)
        {
            if(NULL != pFast)
            {
                pFast = pFast->next;
            }
            //k大于链表的长度
            else
            {
                return NULL;
            }
            i++;
        }
        //快慢指针一起移动
        while(NULL != pFast->next)
        {
            pSlow = pSlow->next;
            pFast = pFast->next;
        }
        return pSlow;
    }
    int hasLoop(LinkNode *head)
    {
            if (head == NULL)
            return 0;
        if(NULL == head)
            return 0;
        LinkNode *slow = head;
        LinkNode *fast = head->next;
        //当快指针到末尾时，无环，结束
        while (NULL != fast  && NULL != slow) 
        {
            //快慢相遇，有环
            if (fast == slow)
                return 1;
    
            slow = slow->next; // 慢指针每次走一步
    
            fast = fast->next;
            if (fast != NULL)
                fast = fast->next;
        }
    
        return 0;
    }
    void printLinkNode(LinkNode *head)
    {
        while(NULL != head)
        {
            NULL == head->next?printf("%d\n",head->val):printf("%d->",head->val);
            head = head->next;
        }
    }
    int main(void)
    {
        NodeVal arr[] = {1,2,3,4,5,6};
        LinkNode *head = NULL;
        head = createLinkNode(arr,sizeof(arr)/sizeof(NodeVal));
        printLinkNode(head);
        LinkNode* findNode =  FindKthToTail(head,3);
        if(NULL != findNode);
            printf("val %d\n",findNode->val);
        destoryLinkNode(head);
        return 0;
    }

--------------------

### **推荐阅读** ###

• [吴师兄实名吐槽 LeetCode 上的一道题目。。。][LeetCode]• [面试字节跳动时，我竟然遇到了原题……][Link 1]• [计算机专业的学生怎样练习编程才能把编程学精通？][Link 2]• [为什么 MySQL 使用 B+ 树][MySQL _ B_]• [一道简简单单的字节跳动算法面试题][Link 3]

--------------------

欢迎关注我的公众号“**五分钟学算法**”，如果喜欢，麻烦点一下“**在看**”~

![format_png 2][]

[format_png]: /images/20221123/17eae2a5964148c497103d5c0d033167.png
[format_png 1]: /images/20221123/8d80e1ffd561440f915d04836197debc.png
[LeetCode]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e75efcd79fcf9c65ebb5070122b9705e18cb1c46b06c5eb3e299520ed4a25e327bc07bb4b&idx=2&mid=2247490158&scene=21&sn=12e587a361f0df072d2dc164c219a61e#wechat_redirect
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e75aecd79fcb8b5f932c7ba5ed7a9e34a6c99f20bc129cef33774167d668e8745755d02ad&idx=1&mid=2247490095&scene=21&sn=baa0379b1ca62db17327a2cb825a1b24#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0d87aacd7a0ebc3ada34a076d1fa3943ee24097966257132b1042b7a3e4debedc78f38c8cf&idx=1&mid=2247493675&scene=21&sn=6b501ef2032ab911f0a3519eb7397017#wechat_redirect
[MySQL _ B_]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e759ccd79fc8a73c77eacfd7c8b1391b08864e2e13fdf5a6e41e218a499d5a87ee12e4e6a&idx=2&mid=2247490077&scene=21&sn=56c52b385c98c7f0ad33c2621da101eb#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e767dcd79ff6b2733dd8905f188afb19eb400d5e644f5b5127f909ee7c3583786031f9c20&idx=2&mid=2247490044&scene=21&sn=bb3610dfedbb2e0c017c3ff3d5e4684b#wechat_redirect
[format_png 2]: /images/20221123/f21b6dae082a4ac5b2e1b178614e2832.png