Ben Sooraj M - 1 year ago 76
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:

``````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)

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

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):

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

``````

### 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
``````

``````2 5 6 9
``````

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)