【数据结构与算法】（二）链表

发布时间：2020-12-16 09:19:24 所属栏目：百科来源：网络整理

导读：环形链表 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x),next(NULL) {} * }; */class Solution {public: bool hasCycle(ListNode *head) { setListNode * address; ListNode* pos

环形链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x),next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        set<ListNode *> address; 
        ListNode* pos=head;
        while(true){
               if(pos==NULL){
                   return false;
               }
               if(address.count(pos)==1){
                   return true;
               }else {
                  address.insert(pos);                   
               }
                   
               pos=pos->next;
               
               
           }
        return true;
                
    }
};

要点：

c++ STL 函数? Set??关联容器支持高效的关键字查找和访问

set.insert(1);

set.count(1)

count()?用来查找set中某个某个键值出现的次数。这个函数在set并不是很实用，因为一个键值在set只可能出现0或1次，这样就变成了判断某一键值是否在set出现过了。

set底层实现方式为RB树（即红黑树）

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!