Python中的循环链表检测？

Question

有没有办法在Python中找到循环链表的第一个元素？在Java和C++中，你可以直接设置一个指针指向第一个元素。

我看到一个问题：给定一个循环链表，写一个算法来返回循环开始的那个节点。

Answer 1

我觉得你需要用深度优先搜索来解决这个问题，下面是一个大概的思路：

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)

Answer 2

循环链表没有真正的开始和结束。不过根据你的评论，我觉得你想要在遍历这个链表的时候，检测到你回到了最开始的那个元素。

#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