LintCode（103）帶環(huán)鏈表 II
來(lái)源：程序員人生 發(fā)布時(shí)間：2016-06-07 08:12:18 閱讀次數(shù)：2832次
題目
給定1個(gè)鏈表，如果鏈表中存在環(huán)，則返回到鏈表中環(huán)的起始節(jié)點(diǎn)的值，如果沒(méi)有環(huán)，返回null。
樣例
給出 ⑵1->10->4->5, tail connects to node index 1，返回10
分析
上1題的進(jìn)階。
首先，利用快慢指針判斷有沒(méi)有環(huán)，若遇到slow == fast時(shí)，跳出循環(huán)；
然后，調(diào)劑fast=head，slow不變，此時(shí)slow與fast同步移動(dòng)，直至再次相遇，即是鏈表中環(huán)的起始節(jié)點(diǎn)。
Python代碼
"""
Definition of ListNode
class ListNode(object):
def __init__(self, val, next=None):
self.val = val
self.next = next
"""
class Solution:
"""
@param head: The first node of the linked list.
@return: The node where the cycle begins.
if there is no cycle, return null
"""
def detectCycle(self, head):
# write your code here
if head == None or head.next == None:
return None
slow = head
fast = head
while fast != None and fast.next != None:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
if fast != None and fast == slow:
fast = head
while fast != slow:
slow = slow.next
fast = fast.next
return fast
return None
GitHub -- Python代碼
C++代碼
/**
103 帶環(huán)鏈表 II
給定1個(gè)鏈表，如果鏈表中存在環(huán)，則返回到鏈表中環(huán)的起始節(jié)點(diǎn)的值，如果沒(méi)有環(huán)，返回null。
您在真實(shí)的
面試中是不是遇到過(guò)這個(gè)題？ Yes
樣例
給出 ⑵1->10->4->5, tail connects to node index 1，返回10
*/
/**
* Definition of ListNode
* class ListNode {
* public:
* int val;
* ListNode *next;
* ListNode(int val) {
* this->val = val;
* this->next = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param head: The first node of linked list.
* @return: The node where the cycle begins.
* if there is no cycle, return null
*/
ListNode *detectCycle(ListNode *head) {
// write your code here
if(head == NULL || head->next ==NULL)
{
return NULL;
}//if
ListNode *slow = head, *fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast)
{
break;
}//if
}//while
if(fast && fast == slow)
{
fast = head;
while(fast != slow)
{
fast = fast->next;
slow = slow->next;
}//while
return fast;
}//if
return NULL;
}
};
GitHub -- C++代碼
生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
