Single Linked List

#1.SingleLinked List.
class Node:
    def __init__(self,value): #initialising the node |data_|link_|
        self.data=value
        self.link=None

class singleLinkedList:
    def __init__(self): #initialising the root element
        self.root=None

    def displayList(self): #for displaying the list elements
        if self.root is None:
            print("List is empty")
            return
        else:
            print("List is: ")
            p=self.root
            while p is not None:
                print(p.data," ",end=" ")
                p=p.link
            print()
    def countNode(self):
        count=0
        p=self.root
        while p is not None:
            count+=1
            p=p.link
        print("No.of nodes in list are:",count)

    def searchNode(self,ele):
        loc=1
        p=self.root
        while p is not None:
            if(p.data==ele):
                print(ele,"Is found in list at",loc)
                return True
            loc+=1
            p=p.link
        else:
            print(ele,"Is not found in the list!")
            return False

    def insertAtBeg(self,data):
        temp=Node(data)
        temp.link=self.root
        self.root=temp

    def insertAtEnd (self,data):
        temp=Node(data)
        if self.root is None:
            self.root=temp
            return
        p=self.root
        while p.link is not None:
            p= p.link
        p.link=temp

    def creatList(self):
        n=int(input("Enter the No of elements you want: "))
        if n==0:
            return
        for i in range(n):
            data=int(input("Enter elemenets in the List: "))
            self.insertAtEnd(data)

    def insertAfterSpecified(self,data,loc):
        p=self.root
        while p is not None:
            if p.data==loc:
                break
            p=p.link
        if p is not None:
            temp = Node(data)
            temp.link = p.link
            p.link = temp

    def insertBeforeSpecified(self,data,loc):
        if self.root is None:
            print("List is empty.")
            return
        if loc==self.root.data:
            temp=Node(data)
            temp.link=self.root
            self.root=temp
            return
        p=self.root
        while p.link is not Node:
            if p.link.data==loc:
                break
            p=p.link
        if p.link is None:
            print(loc,"Not present in this list.")
        else:
            temp=Node(data)
            temp.link=p.link
            p.link=temp

    def insertAtPosition(self,data,loc):
        if loc==1:
            temp=Node(data)
            temp.link=self.root
            self.root=temp
            return

        p=self.root
        i=1
        while i<loc-1 and p is not None:
            p=p.link
            i+=1

        if p is None:
            print("You can only insert till",i)
        else:
            temp=Node(data)
            temp.link=p.link
            p.link=temp

    def deleteFirst(self):
        if self.root is None:
            return
        self.root=self.root.link

    def deleteLast(self):
        if self.root is None:
            return
        if self.root.link is None:
            self.root=None
            return
        p=self.root
        while p.link.link is not None:
            p=p.link
        p.link=None

    def deleteAny(self,data):
        if self.root is None:
            print("List is empty!")
            return
        if self.root.data==data:
            self.root=self.root.link
            return
        p=self.root
        while p.link is not None:
            if p.link.data==data:
                break
            p=p.link
        if p.link is None:
            print("Element",data,"is not in list!")
        else:
            p.link=p.link.link

    def reverseList(self): #take 2 variables: prev p and next.
        prev=None # prev is initialise to none because if behind p and p is start node.
        p=self.root
        while p is not None: #until p is none we'll check
            next=p.link # intialise next as p's successor 
            p.link=prev #p's link as prev
            prev=p #mode prev at p's location
            p=next # move p to next and next to p.link value, I.E prev=1 p=2 and next=3
        self.root=prev

    def bsortByData(self):
        end=None #initialise end as None
        while end!=self.root.link: 
            p=self.root
            while p.link!=end: #until p doesnt reaches or point end we'll check
                q=p.link
                if p.data>q.data: #if value of p's data is greater than value of q's data
                    p.data,q.data=q.data,p.data #swap values
                p=p.link #increment the node
            end=p

    def bsortByLink(self):
        end=None
        while end!=self.root.link:
            r=p=self.root
            while p.link !=end:
                q=p.link
                if p.data>q.data:
                    p.link=q.link
                    q.link=p
                    if p!=self.root:
                        r.link=q
                    else:
                        self.root=q
                    p,q=q,p
                r=p
                p=p.link
            end=p

    def hasCycle(self): #help detecting if there is any loop or self contained cycles in the list.
        if self.detectCycle() is None:
            return False
        else:
            return True

    def insertCycle(self):
        pass

    def detectCycle(self):
        if self.root is None or self.root.link is None: # if list of empty or just one node, we'll return NONR
            return None
        slow=self.root #initialise both fast and slow as root
        fast=self.root #slow will move one node at a time, fast move 2 nodes at a time
        while fast is not None and fast.link is not None:
            slow=slow.link
            fast=fast.link.link
            if slow==fast: # if fast and slow meets it will detect the cycle in the list.
                return slow #return the position of meeting of fast and slow.
        return None

    def removeCycle(self):
        c=self.detectCycle() #c is the point where fast adn slow met.
        if c is None:
            print("Node at which the cycle is detected :",c.data)
        p=c #initialising p and q at the position where fast and slow met.
        q=c
        len_cycle=0 #length of the cycle
        while True:
            len_cycle+=1
            q=q.link   #just moving q and fixing p at c, whenever q==p we'll stop and take the count of nodes as length of cycle.
            if p==q:
                break
        print("length of the cycle is:",len_cycle)
        lrl=0
        p=self.root #to detect remaining nodes initialise p at start and move both p and q
        while p!=q:
            lrl+=1
            p=p.link #the node at which both p and q again meet, is the break point and provide the remaining len of list.
            q=q.link
        print("Node not in the list are:",lrl)
        llist=len_cycle+lrl # adding length of lista d  remaining nodes will give the total length of the list.
        print("Length of list is:",llist)
        p=self.root
        for i in range(llist-1): #looping till total length-1 to remove the cycle by making last node's link as NONE 
            p=p.link
        p.link=None

    def mergelist(self,list2):
        merge_list=singleLinkedList()
        merge_list.root=self._merge2(self.root,list2.root)
        return merge_list

    def _merge2(self,p1,p2):
        if p1.data<=p2.data:
            startM=Node(p1.data)
            p1=p1.link
        else:
            startM=Node(p2.data)
            p2=p2.link
        pM=startM
        while p1 is not None and p2 is not None:
            if p1.data<=p2.data:
                pM.link=Node(p1.data)
                p1=p1.link
            else:
                pM.link=Node(p2.data)
                p2=p2.link
            pM=pM.link
        while p1 is not None: #if list 2 is finished and only list 1 elements left
            pM.link=Node(p1.data)
            p1=p1.link
            pM=pM.link
        while p2 is not None: #if list 2 is left and list 1 finishes
            pM.link=Node(p2.data)
            p2=p2.link
            pM=pM.link
        return  startM

    def mergeLinks(self,list2):
        merge_list = singleLinkedList()
        merge_list.root = self._mergeLinks(self.root, list2.root)
        return merge_list

    def _mergeLinks(self,p1,p2):
        if p1.data<=p2.data:
            startM=p1
            p1=p1.link
        else:
            startM=p2
            p2=p2.link
        pM=startM
        while p1 is not None and p2 is not None:
            if p1.data<=p2.data:
                pM.link=p1
                pM=pM.link
                p1= p1.link
            else:
                pM.link=p2
                pM=pM.link
                p2=p2.link
        if p1 is None:
            pM.link=p2
        else:
            pM.link=p1
        return startM

    def mergesort(self):
        self.root=self.merrec(self.root)

    def merrec(self,list_start):
        if list_start is None or list_start.link is None: #if empty list or only one node found, return NONE
            return list_start
        s1=list_start #initialise first list 
        s2=self.divideList(list_start) #initialise second list
        s1=self.merrec(s1) #recursively sorting list
        s2=self.merrec(s2)
        startM=self._merge2(s1,s2) #calling defined func to sort 2 list and club into one list
        return startM

    def divideList(self,p):
        q=p.link.link
        while q is not  None and q.link is not None:
            p=p.link
            q=q.link.link
        s2=p.link
        p.link=None
        return s2


list=singleLinkedList()
list.creatList()

while True:
    print("1.Display List")
    print("2.Count the no.of nodes")
    print("3.Search a node")
    print("4.Insert in empty list/insert at beginning")
    print("5.Insert at end of list")
    print("6.Insert after a specified node")
    print("7.Insert before a specified node")
    print("8. Insert at given position")
    print("9.Delete first node")
    print("10.Delete last node")
    print("11.Delete any node")
    print("12.Reverse the list")
    print("13.Bubble sort by exchaning Data")
    print("14.Bubble sort by exchaning links")
    print("15.Merge List")
    print("16.Insert Cycle")
    print("17.Detect Cycle")
    print("18.Remove Cycle")
    print("19.Merge sort")
    print("20.Quit")

    choice=int(input("Enter a choice/operation you want to perform:"))
    if choice==1:
        list.displayList()
    elif choice==2:
        list.countNode()
    elif choice==3:
        ele=int(input("Enter the element to be searched: "))
        list.searchNode(ele)
    elif choice==4:
        data=int(input("Enter the data to be inserted: "))
        list.insertAtBeg(data)
    elif choice==5:
        data = int(input("Enter the data to be inserted: "))
        list.insertAtEnd(data)
    elif choice==6:
        data = int(input("Enter the data to be inserted: "))
        loc=int(input("Enter the Location at which data to be inserted: "))
        list.insertAfterSpecified(data,loc)
    elif choice==7:
        data = int(input("Enter the data to be inserted: "))
        loc = int(input("Enter the Location at which data to be inserted: "))
        list.insertBeforeSpecified(data,loc)
    elif choice==8:
        data = int(input("Enter the data to be inserted: "))
        loc = int(input("Enter the Location at which data to be inserted: "))
        list.insertAtPosition(data,loc)
    elif choice==9:
        list.deleteFirst()
    elif choice==10:
        list.deleteLast()
    elif choice==11:
        data = int(input("Enter the data to be deleted: "))
        list.deleteAny(data)
    elif choice==12:
        list.reverseList()
    elif choice==13:
        list.bsortByData()
    elif choice==14:
        list.bsortByLink()
    elif choice==15:
        list.mergelist()
    elif choice==16:
        data = int(input("Enter the data at which the cycle has to be inserted: "))
        list.insertCycle(data)
    elif choice==17:
        if(list.hasCycle()):
            print("List has a cycle..")
        else:
            print("List doesnt have a cycle.")
    elif choice==18:
        list.removeCycle()
    elif choice==19:
        list.mergesort()
    elif choice==20:
        break
    else:
        print("Invalid choice!")