Sort List — LeetCode 148 Python Solution
MediumLinked ListTwo PointersDivide and ConquerSortingMerge Sort
- Problem
- #148
- Pattern
- Linked List
- Reading time
- 5 min
- Source
- leetcode.com
The problem
Given the head of a linked list, return the list after sorting it in ascending order.
Example
- Input
- head = [4,2,1,3]
- Output
- [1,2,3,4]
Python solution
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head is None or head.next is None:
return head
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
l1, l2 = head, slow.next
slow.next = None
l1, l2 = self.sortList(l1), self.sortList(l2)
dummy = ListNode()
tail = dummy
while l1 and l2:
if l1.val <= l2.val:
tail.next = l1
l1 = l1.next
else:
tail.next = l2
l2 = l2.next
tail = tail.next
tail.next = l1 or l2
return dummy.nextComplexity
| Measure | Complexity |
|---|---|
| Time | O(n \times \log n) |
| Space | O(\log n) auxiliary |
Pattern: Linked List
Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 148. Sort List is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Linked List.
The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.
Related problems
On a study list
This problem is on Top Interview 150.
Frequently asked questions
- How hard is LeetCode 148. Sort List?
- LeetCode 148. Sort List is rated Medium on LeetCode.
- What is the time complexity of LeetCode 148. Sort List?
- The Python solution on this page runs in O(n \times \log n).
- What is the space complexity of LeetCode 148. Sort List?
- The Python solution on this page uses O(\log n) auxiliary space.
- What topics does LeetCode 148. Sort List cover?
- LeetCode 148. Sort List is tagged Linked List, Two Pointers, Divide and Conquer, Sorting and Merge Sort on LeetCode.