LintCode（102） 帶環鏈表
來源：程序員人生 發布時間：2016-06-04 15:10:19 閱讀次數：2461次
題目
樣例
給出 ⑵1->10->4->5, tail connects to node index 1，返回 true
分析
判斷鏈表有沒有環的問題，很經典，也是
面試中常見的問題。
快慢指針解決。
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: True if it has a cycle, or false
"""
def hasCycle(self, head):
# write your code here
if head == None or head.next == None:
return False
slow = head
fast = head
while fast != None and fast.next != None:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
GitHub -- Python代碼
C++代碼
/**
102 帶環鏈表
給定1個鏈表，判斷它是不是有環。
您在真實的
面試中是不是遇到過這個題？ Yes
樣例
給出 ⑵1->10->4->5, tail connects to node index 1，返回 true
*/
/**
* 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: True if it has a cycle, or false
*/
bool hasCycle(ListNode *head) {
// write your code here
if(head == NULL || head->next == NULL)
{
return false;
}//if
ListNode *slow = head, *fast = head;
while(fast != NULL && fast->next != NULL)
{
fast = fast->next->next;
slow = slow->next;
if(slow == fast)
{
return true;
}//if
}//while
return false;
}
};
GitHub -- C++代碼
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
