在循环链表中确定节点长度的错误值

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_chain 和 loop_size 中看到一些问题。

在create_chain中，逻辑不清楚，当loop_size == 0时，没有创建链，但我想链应该是创建的循环大小是多少？

另外函数create_chain中循环大小的定义不严格，假设有300个节点，是否可以创建一个长度为300的循环？如果是，这一行 "nodes[num_of_nodes-1].next = nodes[(num_of_nodes - loop_size)-1]" 应该更改。

最大的问题是loop_size函数，我看到你用快慢指针法来计算循环长度，但是快慢法主要用于检测环路，可以找到环路的入口。当你找到循环的入口时，计算循环长度应该很容易，所以我在 loop_size 函数中添加了这个辅助函数。

在函数 loop_size 的 while 循环括号内，它应该是 'and' 而不是 'or'。下面是我重写的 class 和方法。希望这就是您想要的！

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))

在循环链表中确定节点长度的错误值

Wrong value for determining Node length in Circular Linked List

python

data-structures

python-3.x

singly-linked-list