（剑指Offer）面试题56：链表中环的入口结点

题目：

一个链表中包含环，请找出该链表的环的入口结点。

思路：

1、哈希表

遍历整个链表，并将链表结点存入哈希表中（这里我们使用容器set），如果遍历到某个链表结点已经在set中，那么该点即为环的入口结点；

2、两个指针

如果链表存在环，那么计算出环的长度n，然后准备两个指针pSlow，pFast，pFast先走n步，然后pSlow和pFase一块走，当两者相遇时，即为环的入口处；

3、改进

如果链表存在环，我们无需计算环的长度n，只需在相遇时，让一个指针在相遇点出发，另一个指针在链表首部出发，然后两个指针一次走一步，当它们相遇时，就是环的入口处。（这里就不说明为什么这样做是正确的，大家可以在纸上推导一下公式）

代码：

参考在线测试OJ的AC代码

在线测试OJ：

http://www.nowcoder.com/books/coding-interviews/253d2c59ec3e4bc68da16833f79a38e4?rp=3

AC代码：

1、哈希表

/*

struct ListNode {

    int val;

    struct ListNode *next;

    ListNode(int x) :

        val(x), next(NULL) {

    }

};

*/

class Solution {

public:

    ListNode* EntryNodeOfLoop(ListNode* pHead)

    {

		if(pHead==NULL || pHead->next==NULL)

            return NULL;

        set<ListNode*> listSet;

        while(pHead!=NULL){

            if(listSet.find(pHead)==listSet.end()){

                listSet.insert(pHead);

                pHead=pHead->next;

            }

            else

            	return pHead;

        }

        return NULL;

    }

};

2、两个指针（改进）

/*

struct ListNode {

    int val;

    struct ListNode *next;

    ListNode(int x) :

        val(x), next(NULL) {

    }

};

*/

class Solution {

public:

    ListNode* EntryNodeOfLoop(ListNode* pHead)

    {

		if(pHead==NULL || pHead->next==NULL)

            return NULL;

        ListNode* pSlow=pHead;

        ListNode* pFast=pHead;

        // detect if the linklist is a circle

        while(pFast!=NULL && pFast->next!=NULL){

            pSlow=pSlow->next;

            pFast=pFast->next->next;

            if(pSlow==pFast)

                break;

        }

        // if it is a circle

        if(pFast!=NULL){

            pSlow=pHead;

            while(pSlow!=pFast){

                pSlow=pSlow->next;;

                pFast=pFast->next;

            }

        }

        return pFast;

    }

};

巴特西

（剑指Offer）面试题56：链表中环的入口结点

题目：

思路：

代码：

在线测试OJ：

最新文章

热门文章