算法-链表-之查找链表环的入口节点

思路：很自然的想到用map，利用map key-value 键值对的唯一性。遍历链表把每个元素保存到map里面，如果是重复的就不保存，同时就返回这个结果，就是想要的值。但是这样操作下来，空间复杂度是o（n），时间也是o（n），有没有更好的办法？

 1 /*
 2 struct ListNode {
 3     int val;
 4     struct ListNode *next;
 5     ListNode(int x) :
 6         val(x), next(NULL) {
 7     }
 8 };
 9 */
10 #include "iostream"
11 #include 
12 class Solution {
13 public:
14     ListNode* EntryNodeOfLoop(ListNode* pHead) {
15         mapint> m;
16         if(pHead==NULL)
17         {
18             return NULL;
19         }
20         ListNode* temp=pHead;
21         while(temp!=NULL)
22         {
23             if(m.find(temp)==m.end())
24                {
25                     m[temp]=temp->val;
26                }
27        
28             else{
29                 return temp;
30             }
31             temp=temp->next;
32         }
33         return NULL;
34 
35     }
36 };

还有个思路是用双指针快慢法，不过有点绕，这里就不展开了

算法

相关

如何实现LRU（最近最少使用）缓存淘汰算法？

2021.11.16（各排序算法对比）

react dom移动算法

算法第四章上机实验报告

算法第二章实践报告

【莫队算法】

算法第四章实践报告

关于tarjan算法的一些整理

【基础】排序算法学习笔记

常用的排序算法介绍和在JAVA的实现（一）

数据结构与算法之PHP查找算法（哈希查找）

数据结构与算法之PHP查找算法（二分查找）

标签