Python中的循环列表检测

Question

有没有一种方法可以检测Python中循环列表的第一个元素？在Java和C++中，您只需建立一个指向第一个元素的指针。

我遇到的问题是：给定一个循环链表，实现一个在循环开始时返回节点的算法。

Answer 1

循环链表没有真正的开头&终止但从您的评论来看，我认为您希望在循环列表时检测何时到达开始使用的元素。

#The structure of ListNode
class ListNode:
  def __init__(self, val):
    self.val = val
    self.next = None
# Supposes you have a circular linked list and you have a reference to head. You can do as follows to print the whole list. 
current = head.next
while current != head: # stop when it comes back to head
  print current.val
  current = current.next

Answer 2

我认为你需要一个深度优先的搜索来回答这个问题

a = [1,2,3]
b = [4,5,6]
a[1] = b
b[2] = a
def is_list(l):
    try:
        it = iter(l)
        return l
    except TypeError:
        return None
def dfs(a, colors):
    l = is_list(a)
    print 'is_list:', l
    if l:
        if colors.has_key(id(l)):
            print 'cycle detected'
            return l
        colors[id(l)] = ''
        for ll in l:
            dfs(ll, colors)
colors = {}
dfs(a, colors)