剑指offer056

剑指offer056：链表中环的入口结点

题目描述

题目描述
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

解法一：基于快慢指针的方法

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        ListNode* fast = pHead, *low = pHead;
        while (fast&&fast->next)
        {
            fast = fast->next->next;
            low = low->next;
            if (fast == low)
                break;
        }
        if (!fast || !fast->next)
            return NULL;
        low = pHead; //low从链表的头出发
        while (fast != low)
        {
            fast = fast->next;
            low = low->next;
        }
        return low;
    }
};

解法二：基于set的方法

/**********************************************************
基于set的方法
这里用到了STL中的set，set有一个特性就是不能插入相同元素，
这样只需遍历原List一次就可以判断出有没有环，还有环的入口地址。
s.insert(node).second这里在插入的同时也判断了插入是否成功，
如果不成功表明set中已经有该元素了，该元素就是环的入口元素。
**********************************************************/
class Solution2 {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        set<ListNode*> s;
        ListNode* node = pHead;
        while (node != NULL) {
            if (s.insert(node).second)
                node = node->next;
            else
                return node;
        }
        return node;

    }
};

main函数

#include "stdafx.h"
#include <iostream>
using namespace std;


//定义结点
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};

int main()
{


    system("pause");
    return 0;
}