从品牌网站建设到网络营销策划,从策略到执行的一站式服务
已知链表中可能存在环,若有环返回环起始节点,否则返回NULL。
勐海网站建设公司成都创新互联,勐海网站设计制作,有大型网站制作公司丰富经验。已为勐海近1000家提供企业网站建设服务。企业网站搭建\外贸网站建设要多少钱,请找那个售后服务好的勐海做网站的公司定做!
//方法一,使用set求环起始节点。
//遍历链表,将链表中节点对应的指针(地址)插入set。 在遍历时插入节点前,需
//要在set中查找,第一个在set中发现的的节点地址XM代理申请,即是链表环的起点。
//Runtime: 24 ms,Memory Usage: 12 MB。
class Solution
{
public:
Solution(){}
~Solution(){}
ListNode detectCycle(ListNode head)
{
std::set node_set;
while (head)
{
if (node_set.find(head)!=node_set.end())
{
return head;
}
node_set.insert(head);
head = head->next;
}
return NULL;
}
};
/*
//方法二:快慢指针。Runtime: 12 ms,Memory Usage: 9.9 MB。
//时间复杂度为O(n)
class Solution
{
public:
Solution(){}
~Solution(){}
ListNode detectCycle(ListNode head)
{
ListNode* fast = head;
ListNode* slow = head;
ListNode* meet = NULL;
while (fast)
{
slow = slow->next;
fast = fast->next;
if (!fast)
{
return NULL;
}
fast = fast->next;
if (fast==slow)
{
meet = fast;
break;
}
}
if (meet==NULL)
{
return NULL;
}
while (head&&meet)
{
if (head==meet)
{
return head;
}
head = head->next;
meet = meet->next;
}
return NULL;
}
};
*/
int main()
{
ListNode a(12);
ListNode b(34);
ListNode c(31);
ListNode d(41);
ListNode e(51);
ListNode f(61);
ListNode g(71);
a.next = &b;
b.next = &c;
c.next = &d;
d.next = &e;
e.next = &f;
f.next = &g;
g.next =&c;
Solution solve;
ListNode* node = solve.detectCycle(&a);
if (node)
{
printf("%d\n",node->val);
}
else
{
printf("NULL\n");
}
return 0;
}
成都网站建设公司地址:成都市青羊区太升南路288号锦天国际A座10层 建设咨询028-86922220
成都快上网科技有限公司-四川网站建设设计公司 | 蜀ICP备19037934号 Copyright 2020,ALL Rights Reserved cdkjz.cn | 成都网站建设 | © Copyright 2020版权所有.
专家团队为您提供成都网站建设,成都网站设计,成都品牌网站设计,成都营销型网站制作等服务,成都建网站就找快上网! | 成都网站建设哪家好? | 网站建设地图