leetcode_环形链表1/2

2019-02-27

准备考研之际，看看环形链表换换脑子

环形链表

题目

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

示例 1：

1
2
3

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

1
2
3

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

1
2
3

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

分析

感觉讲的还是蛮清楚的，这里有个知识点，就是快慢指针法，我们设想两个人绕着操场跑步，快的早晚会套圈的，如果是环形链表，类似，快指针早晚会追上慢指针的

解法

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head:
            return False
        first = head
        second = head
        while True:
            if first.next is None or first.next.next is None:
                return False
            first = first.next.next
            second = second.next
            if first == second:
                return True

环形链表II

题目

无非多了一个条件，不能修改链表，我们之前的做法就不可以了

分析

我们之前深度遍历用了list，这里感觉也是可以的

解法

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        nodeList = []
        while head:
            if head in nodeList:
                return head
            nodeList.append(head)
            head = head.next
        return None

本文作者： xiaoyuyu
本文链接： http://woaixiaoyuyu.github.io/2019/02/27/leetcode-%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A81-2/
版权声明： 本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。转载请注明出处！