304 North Cardinal St.
Dorchester Center, MA 02124

# Sort List LeetCode Solution

## Problem – Sort List LeetCode Solution

Given the `head` of a linked list, return the list after sorting it in ascending order.

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)?

### Sort List LeetCode Solution in C++

``````  /// Merge two sorted lists into one, the head and tail of the new list is returned
std::pair<ListNode*, ListNode*> merge_lists(ListNode* l1, ListNode* l2)
{
ListNode* tail = nullptr;
while (l1 || l2) {
ListNode** list = (!l2 || l1 && l1->val <= l2->val) ? &l1 : &l2;
*next_ptr = tail = *list;
*list = (*list)->next;
next_ptr = &(*next_ptr)->next;
}
*next_ptr = nullptr;
}

/// Take a list and split it into sublists of the requested size, returns number sublists and remaining list
std::pair<int, ListNode*> split_list(ListNode* head, int sz, ListNode* lists[], int num_lists)
{
int count = 0;
while (head && count < num_lists) {
ListNode* list_tail = nullptr;
}
if (list_tail) {
list_tail->next = nullptr;
}
}
}

{
// Working buffer size, must be an even number
constexpr int buf_sz = 8;
ListNode* buf[buf_sz];

// Initially split list into sublists of size 1, then increase the size until
// the entire list is sorted
for (int step = 1; !done; step *= buf_sz) {
done = true;
int num;
ListNode* tail = nullptr;
do {
// Split the list into increasingly larger sublists
std::tie(num, remaining) = split_list(remaining, step, buf, buf_sz);

// We'll be done if this is the first split this pass and there is no more remaining
done &= (!remaining);

// Keep merging our sublists together until a single sorted list is made
for (; 1 < num; num = (num + 1) / 2) {
// Merge each pair of sublists
for (int i = 0; i < num / 2; ++i) {
std::tie(buf[i], tail) = merge_lists(buf[i * 2], buf[i * 2 + 1]);
}

// If there is an odd number of lists, just move the last one. It will get
// merged next time around
if (num % 2) {
buf[num / 2] = buf[num - 1];
}
}
*next_ptr = buf;
next_ptr = &(tail->next);
} while (remaining);
}

}
``````

### Sort List LeetCode Solution in Java

``````  public ListNode sortList(ListNode head) {
ListNode dummy = new ListNode(0);
ListNode [] list = new ListNode;
boolean done = (null == head);
// Keep partitioning our list into bigger sublists length. Starting with a size of 1 and doubling each time
for (int step = 1; !done; step *= 2) {
done = true;
ListNode prev = dummy;
ListNode remaining = prev.next;
do {
// Split off two sublists of size step
for (int i = 0; i < 2; ++i) {
list[i] = remaining;
ListNode tail = null;
for (int j = 0; j < step && null != remaining; ++j, remaining = remaining.next) {
tail = remaining;
}
// Terminate our sublist
if (null != tail) {
tail.next = null;
}
}

// We're done if these are the first two sublists in this pass and they
// encompass the entire primary list
done &= (null == remaining);

// If we have two sublists, merge them into one
if (null != list) {
while (null != list || null != list) {
int idx = (null == list || null != list && list.val <= list.val) ? 0 : 1;
prev.next = list[idx];
list[idx] = list[idx].next;
prev = prev.next;
}

// Terminate our new sublist
prev.next = null;
} else {
// Only a single sublist, no need to merge, just attach to the end
prev.next = list;
}
} while (null != remaining);
}
return dummy.next;
}
``````

### Sort List LeetCode Solution in Python

``````class Solution(object):
def merge(self, h1, h2):
dummy = tail = ListNode(None)
while h1 and h2:
if h1.val < h2.val:
tail.next, tail, h1 = h1, h1, h1.next
else:
tail.next, tail, h2 = h2, h2, h2.next

tail.next = h1 or h2
return dummy.next

while fast and fast.next:
pre, slow, fast = slow, slow.next, fast.next.next
pre.next = None

``````
##### Sort List LeetCode Solution Review:

In our experience, we suggest you solve this Sort List LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Sort List LeetCode Solution

Find on LeetCode

##### Conclusion:

I hope this Sort List LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions