linked_list.py

class Node():
    def __init__(self, val):
        self.value = val
        self.next = None

    def __repr__(self):
        return str(self.value)

class LinkedList():
    def __init__(self):
        self.value = "dummy"
        self.next = None
        
    def __repr__(self):
       out = ""
       p = self.next
       while p != None:
           out += " -> " + str(p)
           p = p.next
       return out           
            
    def add_at_start(self, val):
        p = self
        tmp = p.next
        p.next = Node(val)
        p.next.next = tmp
    
    def add_at_end(self, val):
        p = self
        while p.next != None:
            p = p.next
        p.next = Node(val)      

    def insert(self, val, loc):
        p = self
        for i in range(loc):
            p = p.next
        tmp = p.next
        p.next = Node(val)
        p.next.next = tmp

    def delete(self, loc):
        p = self
        for i in range(loc):
            p = p.next
        if p != None and p.next != None:
            p.next = p.next.next
            
    def get_item(self, loc):
        p = self.next
        for i in range(loc):
            p = p.next
        return p
            
    def find(self, item):
        p = self.next
        loc = 0
        while p != None:
            if p.value == item:
                return p, loc
            else:
                p = p.next
                loc = loc + 1
        return None     

def add_after_item(p, val):
    tmp = p.next
    p.next = Node(val)
    p.next.next = tmp            

def delete_after_item(p):
    if p != None and p.next != None:
        p.next = p.next.next

# Detecting cycles in linked lists.    
def detect_cycle1(lst):
    p = lst.next
    d = {}
    while True:
        if p == None:
            return False
        elif id(p) in d:
            return True
        d[id(p)] = 1
        p = p.next
        
def detect_cycle2(lst):
   slow = fast = lst
   while True:
       if slow == None or fast == None or fast.next == None:
           return False
       slow = slow.next
       fast = fast.next.next
       if slow is fast:
           return True