👀 Views: 1408 💬 Answers: 1 📅 Created: 2025-06-06

python algorithms linked-lists Python

I'm updating my dependencies and I'm stuck on something that should probably be simple... I'm trying to implement a merge sort algorithm specifically for a singly linked list in Python, but I'm working with a `RecursionError: maximum recursion depth exceeded in comparison`. My implementation is intended to sort nodes based on their values, but it seems to unexpected result with larger lists. Here’s the snippet of my code: ```python class ListNode: def __init__(self, value=0, next=None): self.value = value self.next = next def merge_sort(head): if not head or not head.next: return head # Split the list into halves using the fast-slow pointer approach slow = head fast = head.next while fast and fast.next: slow = slow.next fast = fast.next.next mid = slow.next slow.next = None # Split the list left = merge_sort(head) right = merge_sort(mid) return merge(left, right) def merge(left, right): dummy = ListNode(0) tail = dummy while left and right: if left.value < right.value: tail.next = left left = left.next else: tail.next = right right = right.next tail = tail.next tail.next = left or right return dummy.next ``` I've tried running it with a list of 20 nodes, and it crashes with the recursion depth behavior. I suspect the scenario may be related to how I'm splitting the linked list or handling the base cases. I’ve also considered converting the linked list to an array, sorting it, and then converting it back, but I want to keep the space complexity to O(1) if possible. Any suggestions on how to resolve this scenario or improve my merge sort implementation for linked lists? Thanks! Any ideas what could be causing this? Could someone point me to the right documentation? I'm using Python 3.10 in this project.