Dare2Solve
Given the head of a singly linked list, return the list after sorting it in ascending order.
The input is the head of a singly linked list. The list can have up to 10^5
nodes, and each node contains an integer value. The goal is to sort the linked list in ascending order.
The problem of sorting a linked list can be approached in multiple ways, but a simple and intuitive method is to leverage the power of sorting algorithms available in standard libraries. By extracting the values from the linked list into an array, sorting the array, and then reconstructing the linked list, we can achieve the desired result in a straightforward manner.
Base Case Handling:
head
is None
) or contains only one node (head.next
is None
), return the head
as it is already sorted.Extract Elements:
Sort Elements:
sort
method to sort the elements in ascending order.Reconstruct Linked List:
ListNode
objects, linking them together.Return the Head of the New Sorted List:
O(n log n)
O(n)
.O(n log n)
using a comparison-based sort.O(n)
.O(n log n)
.O(n)
O(n)
space.O(log n)
, but the dominant space usage is the list of elements.class Solution {
public:
ListNode* sortList(ListNode* head) {
if (head == nullptr) {
return nullptr;
}
if (head->next == nullptr) {
return head;
}
// Extract the elements from the linked list
std::vector<int> elements;
ListNode* current = head;
while (current != nullptr) {
elements.push_back(current->val);
current = current->next;
}
// Sort the elements
std::sort(elements.begin(), elements.end());
// Create a new sorted linked list
ListNode* result = new ListNode(elements[0]);
ListNode* resultPointer = result;
for (size_t i = 1; i < elements.size(); ++i) {
resultPointer->next = new ListNode(elements[i]);
resultPointer = resultPointer->next;
}
return result;
}
};
class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head
# Extract the elements from the linked list
elements = []
current = head
while current:
elements.append(current.val)
current = current.next
# Sort the elements
elements.sort()
# Create a new sorted linked list
sorted_head = ListNode(elements[0])
current = sorted_head
for val in elements[1:]:
current.next = new_node = ListNode(val)
current = new_node
return sorted_head
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// Extract the elements from the linked list
List<Integer> elements = new ArrayList<>();
ListNode current = head;
while (current != null) {
elements.add(current.val);
current = current.next;
}
// Sort the elements
Collections.sort(elements);
// Create a new sorted linked list
ListNode result = new ListNode(elements.get(0));
ListNode resultPointer = result;
for (int i = 1; i < elements.size(); i++) {
resultPointer.next = new ListNode(elements.get(i));
resultPointer = resultPointer.next;
}
return result;
}
}
var sortList = function(head) {
// No need to BFS, let's simpy iterate
if (head === null){
return null;
}
if (head.next === null){
return head;
}
let elements = []
while (head != null){
elements.push(head.val);
head = head.next;
}
elements.sort(function (a,b){return a-b});
let result = new ListNode(elements.shift());
let resultPointer = result;
while (elements.length){
resultPointer.next = new ListNode(elements.shift())
resultPointer = resultPointer.next;
}
return result;
};