Wrong value for determining Node length in Circular Linked List

Question

I would like to know what I might be doing wrong in trying to find the number of nodes connected in a loop. Here is my implementation in 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

I defined a function to create a node chain by taking on an arbitrary number of nodes and also a desirable loop length as parameters.

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]

I then defined a function to determine the size of a loop given the initial node which passed as a parameter to the function.

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

I wrote a few tests but this particular assertion did not work, and I'd like to understand why.

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

I get this assertion error;

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

I'd really appreciate some guidance on this. Thanks

Answer 1

I see some problems in create_chain as well as in loop_size.

In create_chain, the logic is not clear, when loop_size == 0, there is no chain created, but I suppose chain should be created whatever the loop size is?

Also the definition of loop size in function create_chain is not strict, suppose there are 300 nodes, is it possible to create a loop of length 300? If it is , this line "nodes[num_of_nodes-1].next = nodes[(num_of_nodes - loop_size)-1]" should change.

The biggest issue is the loop_size function, I see you used the fast slow pointers method to try to calculate the loop length, but the fast and slow method is mainly used for detecting loops, and it can find the entrance of the loop. When you find the entrance to the loop, calculate the loop length should be easy, so I added this helper function within loop_size function.

Within the while loop bracket in function loop_size it should be 'and' instead of 'or'. Below is my rewrite of the class and method. I hope this is what you wanted!

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