[leetcode题解]141.Linked List Cycle(链表环问题)

leetcode题解141.Linked list cycle,给定一个单链表,判断该单链表是否有环问题,这个问题蛮简单的,但是在面试中也是经常被问到的,所以要注意一下。解决这道题的思路就是使用两个指针,一个一次走两步,一个一次走一步,如果有环两者必定在某个位置处相遇,只要快的走到了NULL节点,则说明此链表无环。这就是快慢指针找环法,是比较经典的问题。

c++代码如下:

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;
        bool ret = false;
        
        while(fast != NULL && fast->next != NULL)
        {
            slow = slow->next;
            fast = fast->next->next;
            if (fast == slow)
            {
                ret = true;
                break;
            }
        }
        return ret;
    }
};

python代码如下:

class Solution(object):

    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if head == None or head.next == None:
            return False
        ret = False
        slow = head
        fast = head
        while fast != None and fast.next != None:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                ret = True
                break
        return ret

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解]141.Linked List Cycle(链表环问题)

本文链接地址:http://www.iaccepted.net/algorithm/leetcode/68.html

相关文章



发表评论

电子邮件地址不会被公开。 必填项已用*标注