Backend Engineer
Senior
programming
Design a function to sort a linked list in O(n log n) time using the merge sort algorithm. The function should return the head of the sorted linked list.
Example 1:
Input: head = 4 -> 2 -> 1 -> 3
Output: 1 -> 2 -> 3 -> 4
Example 2:
Input: head = -1 -> 5 -> 3 -> 4 -> 0
Output: -1 -> 0 -> 3 -> 4 -> 5
Constraints:
- The number of nodes in the linked list is in the range [0, 5 * 10^4].
- -10^5 <= Node.val <= 10^5.
```
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def sort_list(head):
if not head or not head.next:
return head
def split(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return head, slow
left, right = split(head)
left = sort_list(left)
right = sort_list(right)
return merge(left, right)
def merge(left, right):
if not left:
return right
if not right:
return left
if left.val < right.val:
left.next = merge(left.next, right)
return left
else:
right.next = merge(left, right.next)
return right
```
Trusted by 100+ professionals preparing for interviews
Trusted by 100+ professionals
50+ Company Question Banks
5+ Supported Languages
Practice More Questions Like This
Generate unlimited interview questions with structured answers, code runner, and AI-powered walkthroughs.
Get Started Free