程序员人生 网站导航

LintCode(102) 带环链表

栏目:php教程时间:2016-06-04 15:10:19

题目

给定1个链表,判断它是不是有环。

样例

给出 ⑵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++代码

------分隔线----------------------------
------分隔线----------------------------

最新技术推荐