题目

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

解答

这道题真的很巧妙，首先我们有了环形链表1这道题的铺垫，就能方便的判断有无环了，但是题目要求我们找到环形链表的入口处，所以需要找个方法:

如图，X、Y、Z分别是起点、入口处、相遇处，我们通过红色框起来的式子可以发现如果有一个从X处出发走了a，有一个从Z出发走了c，最后由于相差(b+c)就是环的长度，所以刚好能在Y处相遇，即得到了入口处。

代码如下：

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

 *     ListNode(int x) : val(x), next(NULL) {}

 * };

 */

class Solution {

public:

    ListNode *detectCycle(ListNode *head) {

        ListNode *pSlow=head,*pFast=head;

        while(pFast && pFast->next)

        {

            pSlow=pSlow->next;

            pFast=pFast->next->next;

            if(pSlow==pFast)

                break;

        }

        if(!pFast || !pFast->next)

            return NULL;

        pSlow=head;

        while(pSlow!=pFast)

        {

            pSlow=pSlow->next;

            pFast=pFast->next;

        }

        return pFast;

    }

};

巴特西

Leetcode:环形链表2

题目

解答

最新文章

热门文章