资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划,从策略到执行的一站式服务

C++链表求环

已知链表中可能存在环,若有环返回环起始节点,否则返回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;

}


分享题目:C++链表求环
URL地址:http://cdkjz.cn/article/jcsedc.html
多年建站经验

多一份参考,总有益处

联系快上网,免费获得专属《策划方案》及报价

咨询相关问题或预约面谈,可以通过以下方式与我们联系

大客户专线   成都:13518219792   座机:028-86922220