溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
已知鏈表中可能存在環，若有環返回環起始節點，否則返回NULL。
//方法一，使用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;
}
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
