Given the head of a linked list, return the list after sorting it in ascending order.
Here’s the [Problem Link] to begin with.
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]
Example 3:
Input: head = []
Output: []
Constraints:
- The number of nodes in the list is in the range
[0, 5 * 104]. -105 <= Node.val <= 105
Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?
Solution 1: Brute Force Approach (Using Array)
Intuition
Think of this like organizing a messy bookshelf! One simple way is to take all the books down, put them in a pile, sort that pile, and then put the books back on the shelf in the correct order. We do the same thing here – extract all values from the linked list, sort them in an array, and then put them back in the same linked list structure.
Detailed Approach
- Extract Values: Walk through the linked list and collect all node values in an array
- Sort Array: Use the built-in sort function to sort the array of values
- Put Back Values: Walk through the linked list again and replace each node’s value with the sorted values
- Return Result: The linked list now contains values in sorted order
Code
class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
values = []
current_node = head
# First pass: Collect all values from the linked list
while current_node:
values.append(current_node.val) # Add current node's value to array
current_node = current_node.next
# Sort the values using built-in sort
values.sort()
# Second pass: Reassign the sorted values to the linked list nodes
current_node = head
index = 0
while current_node:
current_node.val = values[index] # Replace with sorted value
index += 1
current_node = current_node.next
return headCode Explanation
We use a two-pass approach here. In the first pass, we walk through the entire linked list and copy all the values into a regular array. Then we sort this array using Python’s built-in sort function, which is very efficient. In the second pass, we walk through the linked list again and replace each node’s value with the corresponding sorted value from our array. The structure of the linked list remains the same – only the values change.
Dry Run
Let’s trace through: 4 -> 2 -> 1 -> 3
First Pass (Extract Values):
Sort Array:
Second Pass (Put Back Values):
- Node 4 becomes 1:
1 -> 2 -> 1 -> 3 - Node 2 becomes 2:
1 -> 2 -> 1 -> 3 - Node 1 becomes 3:
1 -> 2 -> 3 -> 3 - Node 3 becomes 4:
1 -> 2 -> 3 -> 4
Result: 1 -> 2 -> 3 -> 4
Time and Space Complexity
- Time Complexity: O(n log n) – The sorting step dominates the time complexity
- Space Complexity: O(n) – We store all values in the array
Simplifying It
This approach is like taking notes from a messy notebook, organizing those notes separately, and then rewriting them back in the same notebook in order. It’s easy to understand and implement, but requires extra space to store all the values temporarily.
Solution 2: Optimal Approach (Merge Sort)
Intuition
Imagine you have a huge pile of playing cards to sort. Instead of sorting the entire pile at once, you could split it into smaller piles, sort each small pile, and then merge the sorted piles back together. This is exactly what merge sort does! It’s like having a team of people where each person sorts a small pile, then they work together to combine all the sorted piles into one final sorted pile.
Detailed Approach
- Base Case: If the list has 0 or 1 nodes, it’s already sorted
- Split: Find the middle of the list and split it into two halves
- Conquer: Recursively sort both halves
- Merge: Combine the two sorted halves into one sorted list
- Return: The merged result is our final sorted list
Code
class Solution:
def getMiddle(self, head: ListNode) -> ListNode:
slow = head
fast = head
# Use slow and fast pointers to find middle
while fast.next and fast.next.next:
slow = slow.next # Move slow 1 step
fast = fast.next.next # Move fast 2 steps
return slow # Slow pointer ends at the middle (or just before)
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode() # Dummy node to simplify merging
tail = dummy
# Merge nodes by comparing values
while l1 and l2:
if l1.val < l2.val:
tail.next = l1 # Take smaller value from l1
l1 = l1.next
else:
tail.next = l2 # Take smaller value from l2
l2 = l2.next
tail = tail.next
# Append remaining elements from either list
tail.next = l1 or l2
return dummy.next # Skip the initial dummy node
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next: # Base case: empty or single-node list
return head
# Step 1: Split the list into two halves
mid = self.getMiddle(head)
left = head
right = mid.next
mid.next = None # Disconnect the two halves
# Step 2: Recursively sort the two halves
left = self.sortList(left)
right = self.sortList(right)
# Step 3: Merge the sorted halves
return self.mergeTwoLists(left, right)Code Explanation
This solution uses the divide-and-conquer approach with three helper functions. The getMiddle function uses the tortoise and hare technique to find the middle node. The mergeTwoLists function takes two sorted linked lists and merges them into one sorted list by comparing values. The main sortList function recursively splits the list in half, sorts each half, and then merges them back together. This process continues until we have single-node lists (which are already sorted), then builds up the final sorted list.
Dry Run
Let’s trace through: 4 -> 2 -> 1 -> 3
Initial Call: sortList([4 -> 2 -> 1 -> 3])
- Find middle: between 2 and 1
- Split: left = [4 -> 2], right = [1 -> 3]
- Recursively sort both halves
Left Half: sortList([4 -> 2])
- Find middle: between 4 and 2
- Split: left = , right =
- Base case: both are single nodes, return as is
- Merge and → [2 -> 4]
Right Half: sortList([1 -> 3])
- Find middle: between 1 and 3
- Split: left = , right =
- Base case: both are single nodes, return as is
- Merge and → [1 -> 3]
Final Merge: mergeTwoLists([2 -> 4], [1 -> 3])
- Compare 2 and 1: take 1 →
- Compare 2 and 3: take 2 → [1 -> 2]
- Compare 4 and 3: take 3 → [1 -> 2 -> 3]
- Append remaining 4 → [1 -> 2 -> 3 -> 4]
Result: 1 -> 2 -> 3 -> 4
Time and Space Complexity
- Time Complexity: O(n log n) – We divide the list log n times, and each merge takes O(n) time
- Space Complexity: O(log n) – Due to the recursion call stack (depth of recursion is log n)
Simplifying It
This approach is like organizing a large group of people by repeatedly splitting them into smaller groups, having each small group organize themselves, and then merging the organized groups back together. It’s more complex to understand but very efficient and doesn’t require extra space for storing all values like the brute force approach.
Summary
| Approach | Time | Space | Difficulty | Best For |
|---|---|---|---|---|
| Brute Force (Array) | O(n log n) | O(n) | Easy | Learning the concept |
| Optimal (Merge Sort) | O(n log n) | O(log n) | Hard | Production code |
The merge sort approach is generally preferred because it uses less space while maintaining the same time complexity. However, the brute force approach is more intuitive and easier to understand when you’re first learning about sorting algorithms.
Both solutions achieve the same time complexity, but the merge sort solution is more elegant and space-efficient. It also demonstrates important concepts like divide-and-conquer, recursion, and the two-pointer technique. The key insight is that we can sort a linked list without converting it to an array by cleverly splitting, sorting, and merging the sublists!
For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.
