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* head;
    ListNode* tail = nullptr;
    ListNode** next_ptr = &head;
    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;
    return std::make_pair(head, tail);
  }

  /// 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) {
      lists[count++] = head;
      ListNode* list_tail = nullptr;
      for (int i = 0; i < sz && head; ++i, head = head->next) {
        list_tail = head;
      }
      if (list_tail) {
        list_tail->next = nullptr;
      }
    }
    return std::make_pair(count, head);
  }
  
  ListNode* sortList(ListNode* head)
  {
    // Working buffer size, must be an even number
    constexpr int buf_sz = 8;
    ListNode* buf[buf_sz];

    bool done = (!head);
    // 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* remaining = head;
      ListNode* tail = nullptr;
      ListNode** next_ptr = &head;
      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[0];
        next_ptr = &(tail->next);
      } while (remaining);
    }

    return head;
  }

Sort List LeetCode Solution in Java

  public ListNode sortList(ListNode head) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode [] list = new ListNode[2];
    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[1]) {
          while (null != list[0] || null != list[1]) {
            int idx = (null == list[1] || null != list[0] && list[0].val <= list[1].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[0];
        }
      } 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
    
    def sortList(self, head):
        if not head or not head.next:
            return head
    
        pre, slow, fast = None, head, head
        while fast and fast.next:
            pre, slow, fast = slow, slow.next, fast.next.next
        pre.next = None

        return self.merge(*map(self.sortList, (head, slow)))

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