Algorithms-Reference

LinkedList

Class Definition

import sys

Linkedlist Class

class ListNode(object):
    def __init__(self, x=None):
        self.val = x
        self.next = None
        
def printLL(node):
    while node:
        print (node.val, end="->")
        node=node.next

def populateLL(array):
    node= ListNode(0)
    backup=node
    for element in array:
        node.next=ListNode(element)
        node=node.next
    return backup.next

LinkedList MergeSort

class LLMergeSort(object):
    def getMid(self, llist):
        if llist.next==None:
            return llist, None
        slowp= llist
        fastp= llist.next
        while fastp:
            if fastp.next:
                fastp=fastp.next.next
            else:
                break
            llist=llist.next
        mid= llist.next
        llist.next=None
        return slowp, mid


    def merge(self,list1,list2):
        res= ListNode(0)
        backup= res
        while list1 and list2:
            if list2.val<list1.val:
                res.next=list2
                res=res.next
                list2=list2.next
                res.next=None
            else:
                res.next=list1
                res=res.next
                list1=list1.next
                res.next=None
        res.next = list1 or list2
        return backup.next


    def split(self,llist):
        start,mid=self.getMid(llist)
        if mid== None:
            return start
        else:
            return self.merge(self.split(start),self.split(mid))

        
def runLLMS():
    LL= populateLL([10,9,8,4,7,6,5,3,2,53,1])
    res= LLMergeSort().split(LL)
    print(printLL(res))

runLLMS()

1->2->3->4->5->6->7->8->9->10->53->None