循环链接Lis中确定节点长度的错误值

Question

我想知道在寻找一个循环中连接的节点数时，我可能做错了什么。这是我用python实现的。你知道吗

# Defined Node class
class Node(object):
    data = 0
    def __init__(self, data=None, next_node=None):
        self.data = self.increment()
        self.next = next_node

    def increment(self):
        Node.data += 1
        return Node.data

    def setNext(self, next_node = None):
        self.next = next_node

我定义了一个函数来创建一个节点链，它采用任意数量的节点和一个理想的循环长度作为参数。你知道吗

def create_chain(num_of_nodes, loop_size):
    nodes = [Node() for _ in range(num_of_nodes)]
    if loop_size == 0:
        return nodes[0]
    else:
        for node, next_node in zip(nodes, nodes[1:]):
            node.next = next_node
            # cleaned_nodes.append(node)
        nodes[num_of_nodes-1].next = nodes[(num_of_nodes - loop_size)-1]
        return nodes[0]

然后我定义了一个函数来确定给定初始节点的循环的大小，该节点作为参数传递给函数。你知道吗

def loop_size(node):

    count = 0
    if node == None:
        return 1

    if node.next == None:
        return 1


    slow = fast = node

    while(slow or fast or node.next):
        count += 1
        if fast.next == None:
            #count += 1
            break

        if slow == fast.next or slow == fast.next.next:
            count += 1
            break

        slow = slow.next
        fast = fast.next.next

    return count

我写了一些测试，但是这个特别的断言不起作用，我想理解为什么。你知道吗

def test_very_long_chain(self):
    self.chain = create_chain(3904, 1087)
    self.assertEqual(loop_size(self.chain), 10, 'Loop size of 10 expected')

我得到这个断言错误

AssertionError: 3264 != 10 : Loop size of 10 expected

我真的很感谢你的指导。谢谢

Answer 1

我看到一些问题在创建链以及在循环大小。你知道吗

在create\u chain中，逻辑不清楚，当loop\u size==0时，没有创建链，但是我想应该创建链，不管loop size是什么？你知道吗

另外，函数create\u chain中循环大小的定义也不严格，假设有300个节点，可以创建一个长度为300的循环吗？如果是，则此行“nodes[num\u of \u nodes-1].next=nodes[（num\u of \u nodes-loop \u size）-1]”应该更改。你知道吗

最大的问题是loop\u size函数，我看到你用了快慢指针法来尝试计算循环长度，但是快慢法主要用来检测循环，它可以找到循环的入口。当您找到循环的入口时，计算循环长度应该很容易，因此我在loop\u size函数中添加了这个helper函数。你知道吗

在函数loop\u size中的while loop括号内，它应该是'and'，而不是'or'。下面是我重写的类和方法。我希望这就是你想要的！你知道吗

class Node(object):
  def __init__(self, data=None, next_node=None):
    self.data = data
    self.next = next_node

  def increment(self):
    self.data += 1
    return self.data

  def setNext(self, next_node=None):
    self.next = next_node




def create_chain(number, loop):
  if number <= 0 or loop > number:
    print("Error")
    return
  nodes = [Node(i) for i in range(number)]
  for i in range(number-1):
    nodes[i].setNext(nodes[i+1])
  if loop > 0:
    nodes[number-1].setNext(nodes[number-loop])
  return nodes[0]


def loop_size(node):
  def helper(node):
    #print(node.data)
    count = 1
    temp = node
    while(temp.next != node):
      temp = temp.next
      count += 1
    return count

  if not node:
    return 0
  slow = fast = node
  while(slow and fast and fast.next):
    slow = slow.next
    fast = fast.next.next
    if slow == fast:
      return helper(slow)
  return 0


chain = create_chain(300, 300)
print(loop_size(chain))
chain = create_chain(300, 0)
print(loop_size(chain))
chain = create_chain(300, 130)
print(loop_size(chain))