(head)
| 46 | |
| 47 | # Merge sort for linked list |
| 48 | def merge_sort(head): |
| 49 | if not head or not head.next: |
| 50 | return head |
| 51 | |
| 52 | # Find the middle of the list |
| 53 | slow = head |
| 54 | fast = head.next |
| 55 | while fast and fast.next: |
| 56 | slow = slow.next |
| 57 | fast = fast.next.next |
| 58 | |
| 59 | left = head |
| 60 | right = slow.next |
| 61 | slow.next = None |
| 62 | |
| 63 | left = merge_sort(left) |
| 64 | right = merge_sort(right) |
| 65 | |
| 66 | return merge(left, right) |
| 67 | |
| 68 | |
| 69 | if __name__ == "__main__": |
no test coverage detected