Linked List things

linkedlist.py

import json
import sys

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

def build_list(path):
    """takes a source data path and returns a reference
    to the first node in the list"""
    node_dict = {}
    with open(path) as f:
        data = json.load(f)

        # build node list
        for node in data['nodes']:
            id = node['id']
            n = Node(id=node['id'])
            node_dict[id] = n

        # build links
        for node in data['nodes']:
            this_id = node['id']
            next_id = node['next']
            if next_id:
                node_dict[this_id].next = node_dict[next_id]

        # get start
        start_id = data['start_id']
        return node_dict[start_id]

def print_list(head):

    while head != None:
        print head.id
        head = head.next

def lapping(head):
    """Function takes the assumption that if one node is moving twice as fast, it is going to lap the slower node at some point
    """
    
    node_slow = head
    node_fast = head

    while node_fast != None:
        node_slow = node_slow.next
        node_fast = node_fast.next.next
        if node_slow == node_fast:
            return node_slow

    return None

def hasLoop(head):
    """Function takes the assumption that if one node is moving twice as fast, it is going to lap the slower node at some point
    """
    
    if lapping(head) is not None:
        return True
    else:
        return False

def loopStart(head):

    node_slow = lapping(head)

    if node_slow is None:
        return None

    node_new = head

    while node_new != node_slow:
        node_slow = node_slow.next
        node_new = node_new.next
        # print "slow:", node_slow.id, "new:", node_new.id
    
    start = node_new
    
    return start

def loopLength(head):
    
    if not hasLoop(head):
        return

    length = 1

    start = loopStart(head)
    node = start.next

    while node != start:
        length += 1
        node = node.next

    return length

def main():

    if len(sys.argv) > 1:
        head = build_list(sys.argv[1])
        # print_list(head)
        print "This list has a loop:", hasLoop(head)
        print "The start of the loop is:", loopStart(head).id if loopStart(head) else None
        print "The length of the loop is:", loopLength(head)
    else:
        print "Please define an input list"

if __name__ == '__main__':
    main()