Ben Sooraj M Ben Sooraj M - 3 months ago 6
Python Question

Python implementation of Mergesort for Linked list doesn't work

I couldn't find a simple implementation of

Merge Sort
in Python for
Linked Lists
anywhere. Here's what I tried:

Definition for singly-linked list:



class ListNode:
def __init__(self, x):
self.val = x
self.next = None


Merge Sort Implementation:



def mergeSortLinkedList(A):
# Base case length of 0 or 1:
if A == None or A.next == None:
return A

leftHalf, rightHalf = splitTheList(A)

mergeSortLinkedList(leftHalf)
mergeSortLinkedList(rightHalf)

# The above two lines should be modified to the following. Thanks to the answers.

# leftHalf = mergeSortLinkedList(leftHalf)
# rightHalf = mergeSortLinkedList(rightHalf)

return mergeTheLists(leftHalf, rightHalf)


Split:

def splitTheList(sourceList):
if sourceList == None or sourceList.next == None:
leftHalf = sourceList
rightHalf = None

return leftHalf, rightHalf

else:
midPointer = sourceList
frontRunner = sourceList.next
# totalLength += 1 - This is unnecessary

while frontRunner != None:
frontRunner = frontRunner.next

if frontRunner != None:
frontRunner = frontRunner.next
midPointer = midPointer.next

leftHalf = sourceList
rightHalf = midPointer.next
midPointer.next = None

return leftHalf, rightHalf


Merge:

def mergeTheLists(leftHalf, rightHalf):
fake_head = ListNode(None)
curr = fake_head

while leftHalf and rightHalf:
if leftHalf.val < rightHalf.val:
curr.next = leftHalf
leftHalf = leftHalf.next

else:
curr.next = rightHalf
rightHalf = rightHalf.next

curr = curr.next

if leftHalf == None:
curr.next = rightHalf

elif rightHalf == None:
curr.next = leftHalf

return fake_head.next


Data:



# Node A:
nodeA1 = ListNode(2)

nodeA2 = ListNode(1)
nodeA1.next = nodeA2

nodeA3 = ListNode(9)
nodeA2.next = nodeA3

nodeA4 = ListNode(3)
nodeA3.next = nodeA4

# Node C:
nodeC1 = ListNode(5)
nodeA4.next = nodeC1

nodeC2 = ListNode(6)
nodeC1.next = nodeC2

nodeC3 = ListNode(4)
nodeC2.next = nodeC3

nodeC4 = ListNode(5)
nodeC3.next = nodeC4


Expected output when
mergeSortLinkedList(nodeA1)
is called:

1 2 3 4 5 5 6 9


I get the following instead:

2 5 6 9


I am unable to figure out where the miss is. Please help.

Answer

You don't use the return values from the recursive call. The code should be:

def mergeSortLinkedList(A):
    if A is None or A.next is None:
        return A

    leftHalf, rightHalf = splitTheList(A)

    left = mergeSortLinkedList(leftHalf)
    right = mergeSortLinkedList(rightHalf)

    return mergeTheLists(left, right)

After the call of the function, the argument in some cases doesn't point to the head of the sorted list.

The next bug in the code is usage of undefined variable totalLength.