Given the head of a linked list, return the list after sorting it in ascending order.
Test Cases
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]
Solution
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* sortList(ListNode* head) {
if (head == nullptr || head->next == nullptr) return head;
ListNode *slow = head, *fast = head;
while(fast->next != nullptr && fast->next->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
ListNode *next = slow->next;
slow->next = nullptr;
ListNode *first = sortList(head);
ListNode *second = sortList(next);
return merge(first, second);
}
ListNode* merge(ListNode* first, ListNode* second) {
ListNode *prev = new ListNode();
ListNode *head = prev;
while(first != nullptr || second != nullptr) {
if (first == nullptr) {
prev->next = second;
second = second->next;
}
else if (second == nullptr) {
prev->next = first;
first = first->next;
} else {
if (first->val < second->val) {
prev->next = first;
first = first->next;
} else {
prev->next = second;
second = second->next;
}
}
prev = prev->next;
prev->next = nullptr;
}
return head->next;
}
};/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode slow = head, fast = head;
while(fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode next = slow.next;
slow.next = null;
ListNode first = sortList(head);
ListNode second = sortList(next);
return merge(first, second);
}
private ListNode merge(ListNode first, ListNode second) {
ListNode prev = new ListNode();
ListNode head = prev;
while(first != null || second != null) {
if (first == null) {
prev.next = second;
second = second.next;
}
else if (second == null) {
prev.next = first;
first = first.next;
} else {
if (first.val < second.val) {
prev.next = first;
first = first.next;
} else {
prev.next = second;
second = second.next;
}
}
prev = prev.next;
prev.next = null;
}
return head.next;
}
}