Why am I getting a run time error while sorting a linked list?


  • 0
    S
    # Definition for singly-linked list.
    

    class ListNode:

    def init(self, x):

    self.val = x

    self.next = None

    class Solution:
    # @param head, a ListNode
    # @return a ListNode
    def divideInHalf(self, head):
    slow = fast = head
    prev = None
    while fast!=None:
    fast = fast.next
    if fast:
    prev = slow
    slow = slow.next
    fast = fast.next
    prev.next = None
    return (head, slow)

    def merge(self,firstListHead, secondListHead):
        if not firstListHead:
            return secondListHead
        elif not secondListHead:
            return firstListHead
        result = None
        if firstListHead.val < secondListHead.val:
            result = firstListHead
            result.next = self.merge(firstListHead.next, secondListHead)
        else:
            result = secondListHead
            result.next = self.merge(firstListHead, secondListHead.next)
        return result
        
                
                
    def sortList(self, head):
        if head == None:
            return head
        if head.next == None:
            return head
        (firstHalf, secondHalf) = self.divideInHalf(head)
        sortedFirstHalf = self.sortList(firstHalf)
        sortedSecondHalf = self.sortList(secondHalf)
        mergedList = self.merge(sortedFirstHalf, sortedSecondHalf)
        return mergedList

  • 0
    S

    I am getting this for a very large input case.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.