题目描述

求链表入口结点

样例

1 2 3 4 5 6
2

算法1

用set容器计数， 如果已经存在就返回

时间复杂度

STL容器 set ： http://c.biancheng.net/view/7250.html

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *entryNodeOfLoop(ListNode *head) {
        unordered_set<ListNode*> myset;
        ListNode* cur = head;
        ListNode* res = NULL;

        while(cur) {
            if ( myset.count(cur)) {
                res = cur;
                break;
            }
            myset.emplace(cur);
            cur = cur -> next;
        }
        return res;
    }
};