141. Linked List Cycle

Given a linked list, determine if it has a cycle in it.

Follow up:

Can you solve it without using extra space?

来自 <https://leetcode.com/problems/linked-list-cycle/description/>

思路1：

将出现过的链表元素存在一个列表里，每次访问到下一个元素时查看列表中是否已存在

class ListNode(object):
　　def __init__(self, x):
　　　　self.val = x
　　　　self.next = None
   
class Solution(object):
　　def hasCycle(self, head):
　　"""
　　:type head: ListNode
　　:rtype: bool
　　"""
　　# solution 1 效率很低
　　# 将出现过的对象存储到列表之中
　　　　l = []
　　　　while head != None:
　　　　　　l.append(head)
　　　　　　head = head.next
　　　　　　if head in l:
　　　　　　　　return True
　　　　return False

思路2：

将出现过的链表元素打标签，最简单的标签就是链表的next属性，可以把每个出现过的链表元素都指向链表头，这样如果访问到指向链表头的元素，链表一定是个环（包含两种情况，一种是链表最后一个元素确实指向头元素（一次访问），另一种是链表的最后一个元素指向之前的其他非首元素（二次访问））

 1 class Solution(object):
 2     def hasCycle(self, head):
 3     """
 4     :type head: ListNode
 5     :rtype: bool
 6     """
 7         p = head
 8         while p != None:
 9             pre = p.next
10             if pre == head:
11                 return True
12             p.next = head
13             p = pre
14         return False

141. Linked List Cycle

相关推荐